Knapsack with a fixed number of weights

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.

If there are $n$ items, and the number of different weights is $d$, then the problem can be solved in time $O(n^d)$ as follows:

• Define a configuration as a specification of how many items of each weight are in the knapsack (for example: "10 items of weight 1k, 19 items of weight 2k, 5 items of weight 4k"). The number of configurations is $O(n^d)$ since there are at most $n+1$ options for each weight.

• Construct all configurations in which the sum of weight is at most the knapsack capacity $C$.

• For each configuration specifying to take $z_w$ items of weight $w$, take the $z_w$ highest-valued items of weight $w$.

• Find the configuration leading to the highest total value.

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?

In your case that the sizes are only 1, 2 or 4, the answer is quite easy:

If the knapsack has an odd size, then you pick the most valuable item of size 1 and add it to the last slot.

If the remaining knapsack has a size that is an odd multiple of two, then you pick the most valuable item of size 2, or the two most valuable items of size 1, whichever is more valuable, and put them to the last slot of size 2.

Now the remaining knapsack has a size that is a multiple of 4. You pick the most valuable item of size 4, or the two most valuable items of size 2, or the four most valuable items of size 1, or the most valuable item of size 2 plus the two most valuable items of size 1.

With other sizes, say sizes 2, 3 and 5, things will be more difficult. However, you can sort the items of each size in descending order, and can solve this using dynamic programming.

I suppose the time will be polynomial for every fixed size of weights, with the polynomial depending on the weights. But you can sort the items of each weight in descending order in O (n log n), and if there are m different weights and the size of the knapsack is K, you find the best solution easily in mW steps.

If the weights and K are large, the number of possible sums of weights may be a lot smaller than K. For example if K = 1 billion and three weights >= 100 million, there will be less than 167 possible sums of weights < K.

StackExchange Computer Science Q#118184, answer score: 3