With restrictions, can the knapsack puzzle be solved with a greedy algorithm?

Question

I know that with the knapsack problem in general, there is no known greedy algorithm to solve it. But, say we add the following constraints:

• All items have values equal to their weights (for all i, w(i) = v(i))

• The weights are all powers of 2 (for all w(i) there exists n ∈ N such that w(i) = 2^n).

Now, a knapsack problem with the following constraints can have a greedy algorithm that selects the heaviest item which can currently fit in the knapsack until no item remaining can fit.

---

Will this work or is there really no way the constrained knapsack problem can be solved with a greedy algorithm?

Answer 1

In general, there are two types of knapsack problems, one where you can take part of an item (50% of a bag of sand, for instance) and one where you have to take the whole item. The latter is referred to as the 0/1 knapsack (all or nothing), which is what I believe you are referring to.

The first can be solved greedily taking all of the maximum valued items by unit ($x per pound, for example) until your capacity is about full, then filling the rest with a percentage of the remaining highest valued item by unit. The second, without your constraints, cannot be solved greedily, in general.

Now looking at your constraints. In answering this, I'm assuming that values are by unit not by total because this would change the algorithm. Think $2 item weighs 2 pounds and $8 item weighs 8 pounds versus a 2-pound item is $2 per pound ($4 total) and an 8-pound item is $8 per pound ($64 total), which makes there incentive to take the heavier item first. This can be solved greedily by taking the heaviest item possible first, then second heaviest, and so on until no more items will fit in the bag, which is the algorithm you described.

The reason why this works is the sum of all the values below the maximum available to put in the knapsack is still less that of the maximum available due to having powers of two and the value per pound assumption. Think by putting an 8-pound item (total value = $64), I would be losing the opportunity to put a number of 2 & 4-pound items (total value = $4 and $16, respectively). No matter the weight of the knapsack (equal to or larger than 8), there is no combination of only 2's and 4's that could outvalue the contribution of the 8 (if you're thinking five 4-pound items would at $80 then think that at the same weight one 8-pound item and three 4-pound items is better at $112). Since the heaviest item cannot be outvalued by items below it, it's optimal to take that heaviest item, which gives you a greedy solution.