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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.