CODEWITHSUNDEEP
algorithmknapsack-problem
Shababb Karim
Shababb Karim

Reputation: 3733

Continuous Knapsack Vs. 0-1 Knapsack

Why does greedy approach work for continuous knapsack and not for 0-1 knapsack problem?

Upvotes: 2

Views: 1620

Answers (2)

user2512323
user2512323

Reputation:

For continuous knapsack, you can't have q > 0 of an item with the cost c per unit in an optimal solution, while leaving q' > 0 of an another item with the cost c' > c. Otherwise, you simply replace min(q, q') amount of the first item with the same amount of the second, increasing total cost by min(q,q')*(c' - c).

For 0-1 knapsack, where is a counterexample for a naive greedy algorithm. Consider items with weight 6, 5, 4 and cost 8, 5, 4. Let the total allowed weight be 9. Clearly, optimal solution is to take the second and third items for the total cost of 9, but the first item is worth more, both in absolute value and relative to its weight, so should be selected by `greedy' algorithm.

Upvotes: 2

uday
uday

Reputation: 8730

In 0-1 Knapsack, greedy approach doesn't work because it does want you weigh all the possible combinations because unlike in fractional knapsack, where we can use greedy algorithm to get max profit, the empty space lowers the effective profit per pound(weight) of the load. In 0-1 Knapsack, when we consider whether to include an item in the knapsack, we must compare the solution to the subproblem that includes the item with the solution to the subproblem that excludes the item before we can make a choice.

Hence the solution runs O(nW), where n is the number of items and W is the weight of the items that you can put in the knapsack

Hope it clarifies!

Upvotes: 1

Related Questions