Вино продается у ряда продавцов, у каждого свои условия:
цена за галлон
доступное к продаже количество галлонов
минимальная партия
размер инкремента партии закупки (кто-то продает по одной бутылке, а кто-то только вагонами)
Цель: потратив минимальное количество денег, приобрести необходимое число галлонов вина.
Не могу придумать решение к этой задаче. Вроде как похоже на Задачу о ранцах но как её модифицировать не понятно.
Помоги те пожалуйста с ответом.
Заранее спасибо.
Здравствуйте, gzhernov, Вы писали: G>Не могу придумать решение к этой задаче. Вроде как похоже на Задачу о ранцах но как её модифицировать не понятно.
задача о ранце как решается? мы либо берем эту вещь, либо не берем. вот и ветвление, рассматриваем два случая и т.д.
тут то же самое — совершаем сделку с этим на его условиях или нет и дальше смотрим
стоит еще запоминать все наши попытки найти оптимальные условия в каких-то ограничениях и, чтобы одно и то же не пересчитывать, брать из этой таблички. ну это уже, можно сказать, оптимизация. и без нее работать будет, только медленно
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, gzhernov, Вы писали: G>>Не могу придумать решение к этой задаче. Вроде как похоже на Задачу о ранцах но как её модифицировать не понятно. __>задача о ранце как решается? мы либо берем эту вещь, либо не берем. вот и ветвление, рассматриваем два случая и т.д. __>тут то же самое — совершаем сделку с этим на его условиях или нет и дальше смотрим
__>стоит еще запоминать все наши попытки найти оптимальные условия в каких-то ограничениях и, чтобы одно и то же не пересчитывать, брать из этой таблички. ну это уже, можно сказать, оптимизация. и без нее работать будет, только медленно
Это достаточно очевидно. Могли бы вы показать решение этой задачи?
Здравствуйте, gzhernov, Вы писали:
G>Условие задачи звучит так:
G>Вам нужно купить N галлонов вина.
G>Вино продается у ряда продавцов, у каждого свои условия:
G>цена за галлон G>доступное к продаже количество галлонов G>минимальная партия G>размер инкремента партии закупки (кто-то продает по одной бутылке, а кто-то только вагонами) G>Цель: потратив минимальное количество денег, приобрести необходимое число галлонов вина.
G>Не могу придумать решение к этой задаче. Вроде как похоже на Задачу о ранцах но как её модифицировать не понятно.
В задаче о ранце есть объекты которые имеют массу и стоимость, у вас тут объем и истоимость. Вот найдите эти объекты в условии задачи, пример такого объекта: вагон вина — N галонов, стоимость X. Ну а дальше классическое решение задачи о ранце.
Здравствуйте, gzhernov, Вы писали:
G>Вам нужно купить N галлонов вина.
G>Вино продается у ряда продавцов, у каждого свои условия:
G>цена за галлон G>доступное к продаже количество галлонов G>минимальная партия G>размер инкремента партии закупки (кто-то продает по одной бутылке, а кто-то только вагонами) G>Цель: потратив минимальное количество денег, приобрести необходимое число галлонов вина.
Похоже на типичную задачу целочисленного линейного программирования (ILP = Integer Linear Programming). Для них есть готовые солверы (например, SCIP).
Нужно только правильно систему ограничений и оптимизируемый функционал написать.
У меня еще есть своя реализация простенького ILP-солвера на C#, могу поделиться, если будет интерес. Но до SCIPа ему как до Луны.
Здравствуйте, Qulac, Вы писали:
Q>В задаче о ранце есть объекты которые имеют массу и стоимость, у вас тут объем и истоимость. Вот найдите эти объекты в условии задачи, пример такого объекта: вагон вина — N галонов, стоимость X. Ну а дальше классическое решение задачи о ранце.
Классическое решение использовать не получится. Тут есть существенные отличия:
1) В классической укладке рюкзака нет ограничений на минимальное количество объектов одного типа (минимальный размер партии).
2) В классической укладке объем всех взятых объектов <= объема рюкзака. Здесь, по логике вещей, условие обратное (лишнее можно вылить в себя, но меньше купить никак нельзя).
Можно, конечно, взять готовый алгоритм для рюкзака и допилить его напильником, вопрос лишь в целях ТС.
Если ТС нужно реализовать алгоритм решения задачи в академических целях, то проще будет взять какую-то реализацию "рюкзака" и допилить под свои нужды (или самому написать — ничего сложного там нет).
Если же речь идет о решении реальных бизнес-задач, то лучше использовать готовый солвер ILP.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, Qulac, Вы писали:
Q>>В задаче о ранце есть объекты которые имеют массу и стоимость, у вас тут объем и истоимость. Вот найдите эти объекты в условии задачи, пример такого объекта: вагон вина — N галонов, стоимость X. Ну а дальше классическое решение задачи о ранце.
L>Классическое решение использовать не получится. Тут есть существенные отличия: L>1) В классической укладке рюкзака нет ограничений на минимальное количество объектов одного типа (минимальный размер партии). L>2) В классической укладке объем всех взятых объектов <= объема рюкзака. Здесь, по логике вещей, условие обратное (лишнее можно вылить в себя, но меньше купить никак нельзя). L>Можно, конечно, взять готовый алгоритм для рюкзака и допилить его напильником, вопрос лишь в целях ТС.
L>Если ТС нужно реализовать алгоритм решения задачи в академических целях, то проще будет взять какую-то реализацию "рюкзака" и допилить под свои нужды (или самому написать — ничего сложного там нет). L>Если же речь идет о решении реальных бизнес-задач, то лучше использовать готовый солвер ILP.
Вы не поняли идею. Пусть у одного продавца минимальная партия 10 галлонов по цене 5 рублей за галлон. Инкремент 5 галонов.
Получаются такие объекты:
1. 10 галлонов цена 50 рублей
2. 15 наллонов цена 75 рублей
3. 20 галлонов цена 100 рублей.
и т.д.
Т.е нам сначало нужно сгенерировать эти объекты по условию задачи, а уже потом использовать решение как в задаче о ранце.
Здравствуйте, Qulac, Вы писали:
Q>Вы не поняли идею. Пусть у одного продавца минимальная партия 10 галлонов по цене 5 рублей за галлон. Инкремент 5 галонов. Q>Получаются такие объекты:
Q>1. 10 галлонов цена 50 рублей Q>2. 15 наллонов цена 75 рублей Q>3. 20 галлонов цена 100 рублей. Q>и т.д.
Уговорил, так можно, хотя это может многократно увеличить размерность задачи. Причем обычный алгоритм может еще и перебирать бессмысленные с точки зрения исходной задачи варианты типа 10 по 50 и 20 по 100 вместо 30 по 150.
Плюс, проблема с отличием ограничения по объему никуда не делась. Равно как и вопрос о цели ТС, который вообще первичен.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, Qulac, Вы писали:
Q>>Вы не поняли идею. Пусть у одного продавца минимальная партия 10 галлонов по цене 5 рублей за галлон. Инкремент 5 галонов. Q>>Получаются такие объекты:
Q>>1. 10 галлонов цена 50 рублей Q>>2. 15 наллонов цена 75 рублей Q>>3. 20 галлонов цена 100 рублей. Q>>и т.д.
L>Уговорил, так можно, хотя это может многократно увеличить размерность задачи. Причем обычный алгоритм может еще и перебирать бессмысленные с точки зрения исходной задачи варианты типа 10 по 50 и 20 по 100 вместо 30 по 150. L>Плюс, проблема с отличием ограничения по объему никуда не делась. Равно как и вопрос о цели ТС, который вообще первичен.
Добрый день.
Мне хотелось узнать решение именно в академических целях. Но знаний в этой области видимо не хватает потомоу доработать напильником класическое решение о рюкзаке не получилось.
В интернете нашел решение на гитхабе https://github.com/ushkinaz/JackSparrow но там я достаточно легко подобрал значения при которых данная реализация закупала в два раза больше вина чем требовалось. Как мне кажется это не очень правильно.
Вот и обратился за помощью что бы узнать как все таки можно решить такую задачку
Здравствуйте, gzhernov, Вы писали:
G>Мне хотелось узнать решение именно в академических целях. Но знаний в этой области видимо не хватает потомоу доработать напильником класическое решение о рюкзаке не получилось. G>В интернете нашел решение на гитхабе https://github.com/ushkinaz/JackSparrow но там я достаточно легко подобрал значения при которых данная реализация закупала в два раза больше вина чем требовалось. Как мне кажется это не очень правильно.
Судя по беглому просмотру кода, там реализован лишь "жадный" алгоритм, который совсем не гарантирует оптимальности.
G>Вот и обратился за помощью что бы узнать как все таки можно решить такую задачку
Алгоритм делает следующее:
1) Считает грубую оценку лучшего результата;
2) Генерирует допустимое решение жадным алгоритмом (берет предметы с максимальным отношением ценность/объем). Если его ценность совпала с оценочной, то нам повезло, и ничего больше делать не нужно. Иначе начинается основное веселье:
3) Алгоритм рекурсивно перебирает варианты берем/не берем предмет, при каждом выборе делая оценку максимально возможной ценности ветки перебора. Если эта ценность оказывается ниже той, что уже получена ранее, то ветка отсекается без дальнейшего перебора. Иначе перебор продолжается вплоть до последнего предмета.
Под твои условия, как минимум,
1) придется поправить кусок, который генерирует наилучшую оценку;
2) придется подправить жадный алгоритм с учетом минимальной партии и максимально доступного количества у одного продавца;
3) придется править алгоритм ветвления с учетом минимальной партии, инкрементов и того, что последняя закупка в ветке может приводить к превышению ограничения на объем. Получится более сложный алгоритм ветвления — не просто не брать/брать, а не брать/брать N/брать N + inc/брать N + 2 * inc/...
Можно слегка упростить себе жизнь, выкинув кэширование решений подзадач.
Кэп, ты бы ветку почитал сначала. То, что задача сводится к ILP, уже говорилось, но ТС хотелось решение в стиле BnB (а-ля "укладка рюкзака"). ILPшные солверы, кстати, BnB тоже используют.
Здравствуйте, Lexey, Вы писали:
A>>https://en.wikipedia.org/wiki/Linear_programming
L>Кэп, ты бы ветку почитал сначала. То, что задача сводится к ILP, уже говорилось, но ТС хотелось решение в стиле BnB (а-ля "укладка рюкзака"). ILPшные солверы, кстати, BnB тоже используют.
ТС не в теме, и потому спрашивает. Могу посоветовать LINGO, там закодить рекуррентное отношение и ограничения. Типичная, можно сказать, базовая, задачка для лабораторной работы.
Если ему надо решить ручками- тоже всё придумано до нас https://en.wikipedia.org/wiki/Simplex_algorithm.
Здравствуйте, Artеm, Вы писали:
A>ТС не в теме, и потому спрашивает.
А ты думаешь, что ты лучше знаешь, что ему нужно?
A>Могу посоветовать LINGO, там закодить рекуррентное отношение и ограничения. Типичная, можно сказать, базовая, задачка для лабораторной работы.
Здравствуйте, gzhernov, Вы писали:
G>Условие задачи звучит так:
G>Вам нужно купить N галлонов вина.
А почему про банальный обход графа никто не написал?
Узлы — предложения.
Каждое коммерческое предложение — это Total/Granularity узлов. Надеюсь не надо писать что Total — необходимый объем закупки. A Granularity — вот этот параметр продавца: G>размер инкремента партии закупки (кто-то продает по одной бутылке, а кто-то только вагонами)
Все узлы соеденены со всеми.
Вес перехода к узлу — цена покупки.
Обойдите все вершины из нулевого узла и найдите тот путь, который дает необходимое количество вина при минимальной цене.
G>Заранее спасибо.
что выбрали в итоге?
Update:
Количество узлов можно сильно уменьшить. Вместо Total/Granularity узлов на каждое предложение продавца можно заводить логарифм от этой же дроби узлов
Здравствуйте, VladCore, Вы писали:
VC>Обойдите все вершины из нулевого узла и найдите тот путь, который дает необходимое количество вина при минимальной цене.
А зачем? Нам не нужен путь. Нужен только набор узлов, который можно обойти в произвольном порядке. Перебирать пути — это только увеличивать количество вариантов для перебора.
Здравствуйте, Lexey, Вы писали:
VC>>Обойдите все вершины из нулевого узла и найдите тот путь, который дает необходимое количество вина при минимальной цене.
L>А зачем? Нам не нужен путь. Нужен только набор узлов, который можно обойти в произвольном порядке. Перебирать пути — это только увеличивать количество вариантов для перебора.
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, VladCore, Вы писали:
VC>>Ты серъёзно или манипулировать пытаешься?
L>Я серьезно. Мне интересно услышать, какую пользу ты надеешься извлечь, усложняя и без того сложную задачу.
Похоже манипулируешь. Про пользу и сложность я ничего не писал.
