Алгоритм упаковки & # 8230; вид

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-сложный (что означает, что не известен ни один алгоритм, который полином по «размеру» (число битов - на входе). Но если ваши числа невелики (самое большое «значение» во входных данных, скажем, затраты не имеют значения), тогда существует простое решение для динамического программирования.

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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