Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There is one unit of each item.
The problem can be solved using dynamic programming. Suppose the knapsack capacity is $ C$ , and the most valuable item of weight $ w$ has a value of $ v_w$ . Then, the maximum value of KNAPSACK($ C$ ) is the maximum of the following three values:
KNAPSACK($ v_1$ ,$ C-1$ ), KNAPSACK($ v_2$ ,$ C-2$ ), KNAPSACK($ v_4$ ,$ C-4$ ).
Is there a more efficient algorithm? Particularly, is there a greedy algorithm for this problem?
I tried two greedy algorithms, but they fail already for weights 1 and 2. For example, suppose there are 3 items, with values 100, 99, 51 and weights 2, 1, 1:
- If the capacity is 2, then the greedy algorithm that selects items by their value fails (it selects the 100 while the maximum is 99+51).
- If the capacity is 3, then the greedy algorithm that selects items by their value/weight ratio fails (it selects the 99+51 while the maximum is 100+99).
However, this does not rule out the possibility that another greedy algorithm (sorting by some other criterion) can work. Is there a greedy algorithm for this problem? Alternatively, is there a proof that such an algorithm does not exist?