Алгоритм упаковки ... вид

Question

Учитывая массив элементов, каждый из которых имеет value и cost, Какой лучший алгоритм определяет элементы, необходимые для достижения минимального значения при минимальной стоимости? например:

Item: Value -> Cost 
------------------- 
A  20 -> 11 
B  7 -> 5 
C  1 -> 2 

MinValue = 30 
naive solution: A + B + C + C + C. Value: 30, Cost 22 
best option: A + B + B.   Value: 34, Cost 21 

Обратите внимание, что общая стоимость: соотношение затрат в конце концов, это не имеет значения (A + A даст вам лучшее соотношение цены и качества, но A + B + B является более дешевым вариантом, который попадает минимальное значение).

Answer 1

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

Лучше всего [v] быть минимальной стоимостью для получения значения (точно) v. Тогда вы можете рассчитать значения наилучших [] для всех v, путем (инициализировать все наилучшие [v] до бесконечности и):

best[0] = 0 
best[v] = min_(items i){cost[i] + best[v-value[i]]} 

Тогда посмотрите на лучшее [v] для значений до минимума, который вы хотите, плюс наибольшее значение; самый маленький из них даст вам стоимость.

Если вам нужны фактические предметы (а не только минимальная стоимость), вы можете либо сохранить некоторые дополнительные данные, либо просто просмотреть массив лучших [] s и сделать вывод из него.

Answer 2

Редактировать Этот ответ редактируется из-за неправильной действительности. Следуя советам в этом, вы причиняете вам вред.

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

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

Amenddum Это также может быть NP-полным, но я пока не уверен. В любом случае для всех практических целей этот вариант должен быть намного быстрее, чем наивное решение.

Answer 3

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

NP-harddoes не означает, что это невозможно или даже дорого, это означает, что ваша проблема становится быстрее замедляться при решении более масштабных задач. В вашем случае всего три элемента, вы можете решить это за несколько микросекунд.

Для точного вопроса о том, какой из лучших алгоритмов вообще существует. На нем есть целые учебники.Хороший старт - good old Wikipedia.