Здравствуйте, gzhernov, Вы писали:

G>Мне хотелось узнать решение именно в академических целях. Но знаний в этой области видимо не хватает потомоу доработать напильником класическое решение о рюкзаке не получилось.
G>В интернете нашел решение на гитхабе https://github.com/ushkinaz/JackSparrow но там я достаточно легко подобрал значения при которых данная реализация закупала в два раза больше вина чем требовалось. Как мне кажется это не очень правильно.

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

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

Можешь посмотреть мою реализацию классического рюкзака тут:
https://github.com/Lexey/Algorithms/blob/master/Algorithms/Knapsack.cs

Алгоритм делает следующее:
1) Считает грубую оценку лучшего результата;
2) Генерирует допустимое решение жадным алгоритмом (берет предметы с максимальным отношением ценность/объем). Если его ценность совпала с оценочной, то нам повезло, и ничего больше делать не нужно. Иначе начинается основное веселье:
3) Алгоритм рекурсивно перебирает варианты берем/не берем предмет, при каждом выборе делая оценку максимально возможной ценности ветки перебора. Если эта ценность оказывается ниже той, что уже получена ранее, то ветка отсекается без дальнейшего перебора. Иначе перебор продолжается вплоть до последнего предмета.

Под твои условия, как минимум,
1) придется слегка поравить кусок, который строит стартовую "жадную" оценку;
2) придется подправить жадный алгоритм с учетом минимальной и максимальной возможной закупки у одного продавца;
3) придется править алгоритм ветвления с учетом минимальной партии, инкрементов и того, что последняя закупка в ветке может приводить к превышению ограничения на объем. Получится более сложный алгоритм ветвления — не просто не брать/брать, а не брать/брать N/брать N + inc/брать N + 2 * inc/...

Оценочную функцию, наверное, можно оставить без изменений. Хотя, можно ее улучшить с учетом минимальной партии и инкремента.

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

Здравствуйте, gzhernov, Вы писали:

G>Мне хотелось узнать решение именно в академических целях. Но знаний в этой области видимо не хватает потомоу доработать напильником класическое решение о рюкзаке не получилось.
G>В интернете нашел решение на гитхабе https://github.com/ushkinaz/JackSparrow но там я достаточно легко подобрал значения при которых данная реализация закупала в два раза больше вина чем требовалось. Как мне кажется это не очень правильно.

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

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

Можешь посмотреть мою реализацию классического рюкзака тут:
https://github.com/Lexey/Algorithms/blob/master/Algorithms/Knapsack.cs

Алгоритм делает следующее:
1) Считает грубую оценку лучшего результата;
2) Генерирует допустимое решение жадным алгоритмом (берет предметы с максимальным отношением ценность/объем). Если его ценность совпала с оценочной, то нам повезло, и ничего больше делать не нужно. Иначе начинается основное веселье:
3) Алгоритм рекурсивно перебирает варианты берем/не берем предмет, при каждом выборе делая оценку максимально возможной ценности ветки перебора. Если эта ценность оказывается ниже той, что уже получена ранее, то ветка отсекается без дальнейшего перебора. Иначе перебор продолжается вплоть до последнего предмета.

Под твои условия, как минимум,
1) придется поправить кусок, который генерирует наилучшую оценку;
2) придется подправить жадный алгоритм с учетом минимальной партии и максимально доступного количества у одного продавца;
3) придется править алгоритм ветвления с учетом минимальной партии, инкрементов и того, что последняя закупка в ветке может приводить к превышению ограничения на объем. Получится более сложный алгоритм ветвления — не просто не брать/брать, а не брать/брать N/брать N + inc/брать N + 2 * inc/...

Оценочную функцию, наверное, можно оставить без изменений. Хотя, можно ее улучшить с учетом минимальной партии и инкремента.

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