Непрерывный рюкзак Vs. 0-1 Рюкзак

Question

Почему подход Greedy работает над проблемой непрерывного рюкзака, тогда как тот же подход не работает для проблемы с рюкзаком 0-1?

Answer 1

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

Следовательно, решение выполняется O (ЯО), где п число элементов и W представляет собой вес предметов, которые вы можете положить в ранце

Надеется, что это проясняет!

Answer 2

Для непрерывного рюкзаке, вы не можете иметь q > 0 из пункта со стоимостью c на единицу в оптимальном решении, оставляя q' > 0 в качестве другого элемента со стоимостью c' > c. В противном случае вы просто заменяете min(q, q') сумму первого предмета с той же суммой второго, увеличивая общую стоимость на min(q,q')*(c' - c).

Для рюкзака 0-1, где используется контрпример для наивного жадного алгоритма. Рассмотрим предметы с весом 6, 5, 4 и стоимость 8, 5, 4. Пусть общий допустимый вес равен 9. Очевидно, что оптимальным решением является получение второго и третьего элементов для общей стоимости 9, но первый элемент стоит больше, как по абсолютной величине, так и по отношению к ее весу, поэтому должен быть выбран алгоритмом «жадный».