Решения ранца с дробным рюкзаком подходом

Question

Есть два хорошо известные проблемы ранцевых:

1) Учитывая n элементов, каждый из них имеет свою weight и cost. Нам нужно выбрать предметы, которые будут вписываться в наш рюкзак и иметь максимальную стоимость в сумме. Его можно легко решить, используя dynamic programming.

2) Дробный рюкзак: тот же, что и первый, но мы можем взять не весь товар, а его часть. Эта проблема может быть легко решена с помощью greedy algorithm.

Представьте, что мы используем greedy algorithm из второй проблемы для решения первой задачи. Как я могу доказать, что решение, которое мы получим, не более чем в два раза хуже, чем оптимальное?

Answer 1

Насколько я вижу, жадное решение может быть настолько неэффективным, насколько вы хотите. Представьте себе, что у вас есть рюкзак с емкостью 1 и два (n = 2) пункты:

item weight cost density 
------------------------ 
    A  ε ε  1 <- greedy choice 
    B  1 1-ε  1-ε <- optimal choice 

так жадный алгоритм принимает A с ε стоимости, когда оптимальное решение взять B с 1-ε стоимости. Выбранным (жадным) решением является

(1-ε)/ε = 1/ε - 1 

неэффективен, чем оптимальный. Сделайте ε как можно меньше (скажем, ε = 1e-100) и получите очень неэффективное жадное решение.

Редактировать: в случае целочисленных значений только масштаба только образца выше: у вас есть рюкзак с емкостью X и два (n = 2) элементами

item weight cost density 
------------------------ 
    A  1 1  1 <- greedy choice 
    B  X X-1 1-1/X <- optimal choice 

в этом случае жадное решения

(X - 1)/1 = X - 1 

раз неэффективен, чем оптимальный. Наконец, сделайте X достаточно большим (скажем, X = 1e100)