开发者

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 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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜