Knapsack with a fixed number of weights

Question

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?

Answer 1

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.

Answer 2

My comment didn't address your constraint on the number of distinct weights, but since you don't also constrain the number of distinct values, the result is that the number of distinct ratios is not constrained. This is likely to be a problem for other kinds of greedy orderings.

Let's call the number of distinct weights in an instance of your problem $d$.

I don't know a way to prove that no other possible ordering can work, but here is a strategy that can be used to rule out a particular given ordering. I'll work through this for your greedy-value-descending (GVD) algorithm (even though you already found a counterexample in this case so it doesn't tell you anything new):

The greedy-ratio-descending (GRD) algorithm I described in my comment optimally solves instances of the 0-1 Knapsack problem for which no partial item remains. That means that for some other greedy ordering to be correct, then on any such GRD-solvable problem instance in which all ratios are distinct, it must agree with GRD on the choice of the items to include. (The order doesn't have to be identical -- it is allowed to choose the items to include in a different order.)

Let's start with an arbitrary instance of your problem with some given $d$, which has distinct ratios, too many items to fit completely in the knapsack, all item values at least 3, and which can be solved optimally by GRD, and look for a way to convert this into an instance that has $d'=d+1$ distinct weights and obeys the other constraints (distinct ratios, not all items fit, values $\ge 3$, optimally solvable by GRD), but will confuse GVD. That is, we are designing a function that maps instances to instances. The domain of this function is infinite (e.g., take any instance with distinct ratios and add a "critical" item with weight equal to $C$ minus the sum of the weights of all items "completely" chosen (i.e., with fraction 1) by GRD, and choose the item's value to make its ratio halfway between $v_i/w_i$ and $v_{i+1}/w_{i+1}$); if we can show that the range is also infinite (e.g., because the function is one-to-one), then we have established that GVD will produce the wrong answer on an infinite number of problem instances that use $d'$ distinct weights.

One possible transformation is: Multiply all values by $4M$, where $M$ is the product of all distinct weights, and multiply the capacity and all weights by 2. Take the last item chosen by GRD, which has ratio $4Mv_m/2w_m$, and split it nearly in half: one item with value $2Mv_m+1$ and weight $w_m$, and one with value $2Mv_m-1$ and weight also $w_m$. (Multiplying numerators by $M$ ensures that all ratios are integral; the slightly different numerators serve to keep all ratios distinct, since all other ratios are $0 \mod 4$.) Finally add a "decoy" item with value $4Mv_m-3$ and weight $2w_m$. This construction adds at most one new distinct weight, namely $w_m$, so $d' \le d+1$.

The (unique optimal) solution produced by GRD on this new instance will correspond to the (unique optimal) solution it produced to the original instance, choosing both "halves" of the critical item and excluding the decoy, for which there is no room left. OTOH, since we required $v_i \ge 3$ for the input instance, then in particular $v_m \ge 3$, implying $4v_m-3 > 2v_m+1$, so GVD will consider the higher-valued "decoy" item before either half of the critical item -- so at that time it will pick this item if it has room, necessarily resulting in a suboptimal solution (and if it doesn't have room, then it must be because it has already picked items not picked by GRD, which also leads to a suboptimal solution on account of our assumption that the optimal solution is unique).

This instance mapping is injective: different-size inputs map to different-size outputs, and for two differing inputs of the same size, there is a smallest-ratio item that appears in exactly one of the two inputs, and which leads to an output item that does not appear in the other output.