Задача в вакансии

У меня так и не совпало, а ошибку, код выше, так и не нашёл

мне показалось, что в условии можно продавать только одну акцию за раз

В каждый момент времени инвестор может сделать одно из действий:

Купить одну акцию по текущей цене
Продать одну акцию по текущей цене, если у него есть акции
Ничего не делать

Учитывается то и другое. Без первого решение будет — продавать на каждом шаге. А второе — просто часть итоговой формулы.

А ты учитываешь что на последнем шаге можно продать больше 1 акции(и нужно)? У меня вобще выпали данные с максимумом в последнем шаге, т.е. я все время только покупал и в последней итерации продал все.

В таком случае поздравляю!

Running total — это running total по числу акций. Оно не может быть отрицательным

Но разве в гифе не ставится условием, что оно меньше или равно нулю? Да и значения у него отрицательные часто встречаются.Насколько я понял, его значение получается как сумма значения предыдущего runing total с текущим decision. Ещё в условии явно не сказано, что у инвестора сначала нет акций, но из твоего решения видно, что он их на первом шаге начинает продавать. А я мучаюсь предполагая, что у него их нет :)

И ещё не заметил условия, что он может в конце всё продать, но вот почему runing total может принимать отрицательные промежуточные значения я так и не понял.

Ещё в условии явно не сказано, что у инвестора сначала нет акций

Да ладно :)

В момент времени T=0 у инвестора нет акций.

Там скорей инвертированы значения решений, если так можно сказать. и -1 это покупка акции, т.е. у тебя денег стало -1*«цена акции», а когда продал акцию, увеличилось на 1*«цена акции».

так я так и считал тоже в calc "-1" уменьшение суммы, «+1» увеличение, но странно то, что если общая тенденция - уменьшение цены акции, то ответ получается такой же, а если общая стоимость к концу растёт, то ответ неверен по этому решению :(

Проверил, так и есть.

Возможно, я в знаках запутался. Decision равно -1, если мы покупаем акции. Decision * цену = изменению баланса. Поэтому в колонке с суммами «числа акций» всегда отрицательные числа.

Я уже выбросил ту таблицу, но похоже, что в ней была ошибка знаке в финальной сумме, где продаём всё, что осталось.

И ещё не заметил условия, что он может в конце всё продать

Может поэтому не сходится, хотя тогда число должно было получиться меньше, чем правильное.

угу, а то я уже запутался, но если цена имеет тенденцию к росту, то уже почему-то не прокатывает такое решение, странно

Ещё раз посмотрел. У меня там точно ошибка была, в финальной формуле минус должен быть вместо плюса. Мне просто повезло, что цена под конец болталась где-то посередине.

Продать все - просто ставишь в последнию ячейку ограничивающую продажу 100 и все.

просто ставишь в последнию ячейку ограничивающую продажу 100

Или ограничения оставляешь те же, но к сумме добавляешь (- G102*B102).

но если цена имеет тенденцию к росту, то уже почему-то не прокатывает такое решение

Сейчас взял новые данные, они как раз имеют максимум в самом конце, и сделал табличку заново. Получил решение «покупай всё, в конце продашь».

И заводить колонки для ограничений не нужно было, оказывается. Число, если оно одно для всех, можно прямо в решателе указывать, он понимает.

тогда мне всё равно нужно найти ошибку, почему для случая, ссылку на который привели выше, у меня получилось больше чем по их решению (где-то накосячил) и добавить условие, что если максимум на рассматриваемом отрезке находится в конечной точке, то её не выкалываем, а оставляем в массиве

Сумму ты увеличиваешь всегда, а минимальный элемент удаляешь не всегда. И алгоритм у тебя жадный. Ты уверен, что он всегда даст корректный результат? Это нужно доказывать.

Минимальный элемент я не удаляю, когда он совпадает с максимальным из оставшихся точек, который при этом является крайней левой точкой, иначе ругается, что не может удалить несуществующий элемент. Всё равно переделать нужно.

Короче, вот алгоритм, код писать лень.

У нас n элементов. Сортируем по стоимости. А потом цикл, i = 1:n/2

Выбираем i самых дорогих для продажи. Потом идем по первоначальной последовательности, если встречаем наш элемент на продажу на месте j, покупаем самый дешевый на 1:j-1.

Как-то так. Может, надо немного поправить, чтобы в конце можно было продать по конечной цене остатки. Возмжно, мой алгоритм совпадает с каким-нибудь, тут уже описанным.

Ну и максимум по результатам из i берется, забыл упомянуть.

Добрался до компа. Чуть подправил ещё условия для решателя Calc: значения принятия решения меняются в ячейках кроме последней, в последней ссылка на оставшееся число акций на предпоследнем шаге, а для количества акций оставшихся после последнего шага добавил условие равенства нулю. Тогда можно просто сумму макстмизировать. На вид путь получается таким же как в приведённом выше решении. Численный ответ такой же.

Но своём подправленном решении так и не удалось получить такой же ответ. Не могу понять, почему подход поиска пары максимум-минимум(левее макс.) не срабатывает. Последнее значение я не удаляю, если оно максимальное (хранится до конца). Путь решения совпадает до момента, когда слева остаются 2 одинаковых значения стоящих рядом, но не совпадающих по индексу.

Выложи файл электронных таблиц куда-нибудь.

Параметры решателя в файле почему-то не сохраняются, поэтому вот файл, принтскрин настроек решателя. Значение ячейки «C102» (выделена зелёным) задаётся равным количеству акций в ячейке «E101», то есть это условие, что последним шагом продаются все акции. Ответ 10750.

Вот ещё неудачная попытка решить поиском пар покупка(на при минимальной цене)-продажа(при максимальной) с «выкалываением» точек кроме последней, получается 10580, что меньше максимального. Почему такой способ не подходит пока не понял, нужно проверить не становится ли число акций на руках отрицательным в какой-то момент. Правильное решение на питоне выше уже давали.

Почему такой способ не подходит пока не понял

Возможно ты ищешь не ближайший максимум и случайно отбираешь чужую продажу

1. 10
2. 1000
3. 900
4. 1000
5. 5

К 10 - П 1000 (4 шаг)

1. -
2. 1000
3. 900
4. -
5. 5

Да, такая ошибка тоже была. Исправил, но её исправление мне не помогла. Даже переписал, чтобы массив не уменьшался, а просто номера добавлялись в отдельный массив и проверялось нет ли текущего индекса в нём. Уже даже с конца пробовал двигаться. У меня всё до определённого момента хорошо, а потом остаётся точка, которая вместо пропуска является точкой продажи.

У тебя получилось (на тестовом файле, который здесь выкладывали)?

Не, подбором пар минимум-максимум эту задачу правильно не решить, уже проверил и для алгоритма «ищем минимум и ближайший максимум справа» и «ищем первый максимум (если их несколько одинаковых) и минимум слева от него» - не получается. Похоже, что это чистая задача линейного программирования и предложенное выше правильное решение на питоне (с использованием «динамического программирования»), похоже, самый быстро реализуемый способ решения.

я пока больше не занимался. Может быть в выходные к ней вернусь.