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 mini开发者_开发技巧mum weight to the knapsack)?
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.
精彩评论