With restrictions, can the knapsack puzzle be solved with a greedy algorithm? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T02:52:03Z https://cs.stackexchange.com/feeds/question/81715 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/81715 1 With restrictions, can the knapsack puzzle be solved with a greedy algorithm? Andrew Raleigh https://cs.stackexchange.com/users/68680 2017-09-26T19:36:46Z 2017-09-26T19:36:46Z <p>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: </p> <p>• All items have values equal to their weights (for all \$i\$, \$w_i = v_i\$)</p> <p>• The weights are all powers of 2 (for all \$w_i\$ there exists \$n ∈ N\$ such that \$w_i\$ = \$2^n\$).</p> <p>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.</p> <hr> <p>Will this work or is there really no way the constrained knapsack problem can be solved with a greedy algorithm?</p>