Поиск максимальной загрузки мощностей для 0-1 Многомерного рюкзака

Question

Типичная целевая функция многомерного рюкзака 0-1 - максимизировать значение всех предметов в рюкзаке. Хороший алгоритм был предоставлен в ссылке Stackexchange здесь: 0-1 Multidimensional Knapsack.

Однако, если моя целевая функция состоит в том, чтобы как можно больше упаковать как можно больше предметов в рюкзак? Все части имеют равные значения. Сообщение Stackexchange (Knapsack problem with all profits equal to 1) утверждает, что одномерный ранце с равными значениями может быть разрешен алгоритмом Жадного. Это правда? Я думал, что проблема рюкзака 01 - NP-hard, поэтому жадный алгоритм может не дать оптимального решения.

Итак, мои вопросы состоят из двух частей? 1) Может ли оптимальное решение быть задано жадным алгоритмом в этом случае? 01 с равными значениями 2) как реализовать многомерный жадный алгоритм? vi/wi - значение, деленное на вектор ...

Answer 1

1.) Проблема с рюкзаком - проблема NP-Hard. Короче говоря, нет, вы не можете решить его оптимально, используя жадный алгоритм. Вместо этого существуют эвристические подходы, которые могут приблизиться к вам.

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

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