Solving knapsack with fractional knapsack approach

Question

There are two well-known knapsack problems:

1) Given n items, each has its weight and cost. We need to select items, that will fit in our knapsack and have maximal cost in sum. It can be easily solved using dynamic programming.

2) Fractional knapsack: same as the first, but we can take not the whole item only, but its part. This problem can be easily solved with greedy algorithm.

Imagine we are using greedy algorithm from second problem to solve the first one. How can I prove, that the solution we will get is no more than two times worse, than the optimal one?

You probably have more restrictions, since general case (weight, cost are double values, not simply int values) is not so DP-friendly — Alexander Anikin
@Alexander Anikin: int is not a restriction - just scale up my answer - knapsack with 1e100 volume; item A with weight = 1 and cost = 1 and item B with weight = 1e100 and cost 1e100-1 — Dmitry Bychenko

Dmitry Bychenko Dmitry Bychenko · Accepted Answer · 2016-12-13T11:48:04

As far I can see, the greedy solution can be as much as inefficient as you want. Imagine that you have a knapsack with capacity 1 and two (n = 2) items:

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

so the greedy algorithm takes A with ε cost when the optimal solution is to take B with 1-ε cost. The chosen (greedy) solution is

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

times inefficient than optimal one. Make ε as little as you want (say, ε = 1e-100) and have a very inefficient greedy solution.

Edit: in case of integer values only, just scale the sample above: you have a knapsack with capacity X and two (n = 2) items

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

in this case the greedy solution is

   (X - 1) / 1 = X - 1

times inefficient than optimal one. Finally, make X to be large enough (say, X = 1e100)

Solving knapsack with fractional knapsack approach

1 Answers