CODEWITHSUNDEEP
algorithmknapsack-problem
Yuri Stuken
Yuri Stuken

Reputation: 13600

Knapsack problem with all profits equal to 1

There is a variation of knapsack problem when all profits are equal to 1. It seems it can be solved much faster than classical discrete (0-1) knapsack problem, but how? Will just greedy algorithm work (on each iteration put an object with minimum weight to the knapsack)?

Upvotes: 5

Views: 2039

Answers (1)

NPE
NPE

Reputation: 500495

I should think so.

Intuitively, given that all profits equal one, on the profit side you're indifferent to which items you select, you just want as many as you can. The greedy algorithm will give you exactly that.

Upvotes: 4

Related Questions