Каморка

Для задачи оптимизации покупок.
Ну, например, есть односвязный список товаров:

struct Goodie
{
float price;
float quality;
Goodie* next;
};

И нужно написать функцию, которая в пределах бюджета соберет максимальный quality. Ну, скажем:

Goodie* CreateBusket( Goodie* list, float budget );

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

Время исполнения очень критично, но к счастью, списки довольно маленькие - порядка десятков.

Наверняка ведь напридумывано уже до фига алгоритмов, швырните в меня ключевыми словами. Куда копать?

Раздел называется Линейное программирование. Ключевые слова алгоритма - симплекс-метод, если мне память не изменяет..

Дима писал(а):Раздел называется Линейное программирование. Ключевые слова алгоритма - симплекс-метод, если мне память не изменяет..

Да, я думал об этом. Но, откровенно говоря, пока не придумал, как к этой задаче симплекс-метод приложить..

Дима писал(а):Раздел называется Линейное программирование.

йеп

И точно, не изменяет. Вот популярная статья по этому поводу. http://www.kgtu.runnet.ru/WD/TUTOR/lp/lp03.html
Правда, в твоем случае неравенство одно - ограничение на бюджет. Целевая функция - суммарное качество.
Очевидно, что твой случай - вырожден, и оптимальное решение - взять продукт, у которого соотношение цена-качество лучще всего Если же появляются другие ограничения, то без ЛП не обойтись.

Подозреваю еще, что в твоем случае речь идет только о целочисленных решениях. Тогда ты попал Вот полезная ссылочка. http://www.sampo.ru/~alexeyf/lp_faq.html

Эта задача называется 0-1 knapsack problem. Если price была бы в целых числах, можно было бы решить за время O(n*b), n - количество товаров в списке, b - бюджет (например в центах), и с дополнительным местом размером O(b). В общем случае, b - диапазон значений бюджета - например для float - все представимые значения от 0 до budget, что делает решение непрактичным.

Если нужен код для целочисленной версии, могу написать пример.

ajkj2em писал(а):

Дима писал(а):Раздел называется Линейное программирование.

йеп

фукция(ции) качество/товар там не задана. Целевая функция будет вовсе не линейной. Возможность представления фунции цели в виде суммы - не признак линейности. Каждое из "слагаемых" может быть нелинейной, вообще разрывной функцией.

Я, похоже, плохо объяснил условие.
Суть в том, что товаров можно взять много, причем не важно, сколько. Важно, чтобы суммарное качество было максимальным при цене укладывающейся в бюджет.

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

Ну, на самом деле, просто отбрасываю все не помещающиеся в бюджет, а остатки сортирую по качеству. И беру сверху до тех пор, пока в бюджете есть место.

Как ни странно, работает прилично. Хотя оптимального решения и не дает. Хотелось бы находить оптимальное. Да и выполняться побыстрее не мешало бы..

Старина Зотин писал(а):Я, похоже, плохо объяснил условие.
Суть в том, что товаров можно взять много, причем не важно, сколько. Важно, чтобы суммарное качество было максимальным при цене укладывающейся в бюджет.

Товаров можно взять много - это значит можно из данного списка взять несколько или каждого товара из списка можно больше чем один взять (например 10 товаров типа а, 20 типа б и т.д.)?

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

Ну, на самом деле, просто отбрасываю все не помещающиеся в бюджет, а остатки сортирую по качеству. И беру сверху до тех пор, пока в бюджете есть место.

Как ни странно, работает прилично. Хотя оптимального решения и не дает. Хотелось бы находить оптимальное. Да и выполняться побыстрее не мешало бы..

Вот пример на котором это решение дает ответ далекий от оптимального:

товар 1 - цена 6, качество 51
товар 2 - цена 5, качество 50
товар 3 - цена 5, качество 50
бюджет 10

Ваш алгоритм дает 51 вместо 100.

А быстрого оптимального решения к сожалению нет - если конечно кто нибудь не докажет что P=NP

Старина Зотин писал(а):

Дима писал(а):Раздел называется Линейное программирование. Ключевые слова алгоритма - симплекс-метод, если мне память не изменяет..

Да, я думал об этом. Но, откровенно говоря, пока не придумал, как к этой задаче симплекс-метод приложить..

задача о ранце это. там есть алгоритм кк решать.

О, спасибо. Knapsack problem - то что нужно.

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

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

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

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

Старина Зотин писал(а):Для задачи оптимизации покупок.
Ну, например, есть односвязный список товаров:

struct Goodie
{
float price;
float quality;
Goodie* next;
};

И нужно написать функцию, которая в пределах бюджета соберет максимальный quality. Ну, скажем:

Goodie* CreateBusket( Goodie* list, float budget );

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

Время исполнения очень критично, но к счастью, списки довольно маленькие - порядка десятков.

Наверняка ведь напридумывано уже до фига алгоритмов, швырните в меня ключевыми словами. Куда копать?

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

.

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