Каморка

nemiga писал(а): Вводим параметр товара "отношение качество-цена" (Goodie.value:=Goodie.quality/Goodie.price). Сортируем все товары по убыванию параметра value и отбираем сверху, пока денег хватит.

Ну например так:

товар 1 - цена 6, качество 61
товар 2 - цена 5, качество 50
товар 3 - цена 5, качество 50
бюджет 10
получаем 61 а не 100

Старина Зотин писал(а):Самое забавное, что эта фигня, которую я написал в виде прототипа, оказывается, называется громким именем Martello and Toth greedy approximation algorithm.

Наверное, чуваки очень долго думали..

Кстати, мне придется с ним и остаться. Динамическое программирование в моем случае не работает. Я с целью упрощения не все рассказал о задаче. На самом деле у меня каждый предмет представляет из себя дерево предметов, суммарное value которых составляет value корня, ну и price, соответственно распределяется по ветвям. Если дерево перестает помещаться, его можно раздробить и включать отдельные ветви. В этом случае этот самый Martello and Toth обеспечивает довольно плотное заполнение (хотя и не оптимальное, но не слишком от него далекое - явно больше V/2, как с линейным списком), а кроме того я придумал, как все сделать за один проход дерева.

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

Интересная задача, а поподробней можно?

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

Старина Зотин писал(а): Динамическое программирование в моем случае не работает.

Не только в твоём. При шести и большей размерностях - задача практически не решается. Вернее очень медленно.

Поподробней можно, но боюсь утомить.

В общем, никаких роботов-покупателей я, разумеется, не пишу, а просто занимаюсь оптимизацией.

Задача примерно такая. Есть некий массив данных, который рассчитывается при прохождение через дерево в котором каждая нода делает какой-то свой вклад в рассчет. Ноды бывают разных типов и на рассчет у них уходит разное время. Одна из нод занимается тем, что сводит результаты своих детей с соотв. присвоенными весами. Ее называют BlendNode, а операцию сведения blending. Собственно, именно blend nodes и обеспечивают ветвление (на самом деле, не только они, но это уже детали - для нашей задачи достаточно считать, что только они).

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

Ну, например, мы говорим, что ради оптимизации готовы потерять 5% точности результата. То есть, можно на 5% наотбрасывать нод. Причем желательно выбрать такие, которые выполняются подольше.
Ну то есть, та самая проблема ранца, но несколько усложненная ограничениями накладываемыми деревом.

Вопрос состоит в том, чтобы алгоритм поиска не перевесил выигрыш от выбрасывания нод. То, что я пока написал смотрится относительно неплохо - выполняется за линейное время O(N) (N - количество blends в дереве), абсолютное время выполнения порядка половины миллисекунды на дерево содержащее 100 blend nodes.
При потере точности 10% из 100 blends дерева вырезается в среднем около 60 нод. Время выполнения одной ноды сильно разнится в зависимости от типа, но в среднем это 0.1-0.2 миллисекунды. То есть, с моим алгоритмом в этом случае выигрывается 5 ms (что вдвое быстрее). По нашим меркам, это очень много.

любопытно. а как дерево меняется между итерациями ?
оно строится с нуля, оно пересобирается из текущего ?

поинт в том, чтобы посмотреть нельзя ли incrementally пересчитывать knapsack contents ..

Строится с нуля.

anton2 писал(а):

nemiga писал(а): Вводим параметр товара "отношение качество-цена" (Goodie.value:=Goodie.quality/Goodie.price). Сортируем все товары по убыванию параметра value и отбираем сверху, пока денег хватит.

Ну например так:

товар 1 - цена 6, качество 61
товар 2 - цена 5, качество 50
товар 3 - цена 5, качество 50
бюджет 10
получаем 61 а не 100

Пример искусственный: бюджет соизмерим с ценой товара. Я проверял на random выборке с большим бюджетом -- работает со свистом.

.

Ну так он и в жизни может оказаться соизмерим.

anton2 писал(а):

nemiga писал(а): Вводим параметр товара "отношение качество-цена" (Goodie.value:=Goodie.quality/Goodie.price). Сортируем все товары по убыванию параметра value и отбираем сверху, пока денег хватит.

Ну например так:

товар 1 - цена 6, качество 61
товар 2 - цена 5, качество 50
товар 3 - цена 5, качество 50
бюджет 10
получаем 61 а не 100

Еще можно попробовать так. Вводим кредит. Если денег не хватает, занимаем в долг. При этом параметр value вещи, купленой в долг, уменьшаем по той или иной формуле -- чем больше под эту вещь заняли, тем больше уменьшаем*.

Дальше, когда корзина заполнится, сортируем все вещи по "чистому" value (без учета сколько под какую занимали) и начинаем отдавать долг, выбрасывая сначала те, у которых value меньше.

*Примечание: да, даже с заемом может так получится, что самую лучшую вещь не купишь, но по-моему, этот алгоритм лучше простого greedy.

.