所有利润等于1的背包问题 [英] Knapsack problem with all profits equal to 1

问题描述

当所有利润都等于1时，背包问题会有一个变化.看来它比经典的离散(0-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)?

推荐答案

我应该这样认为.

直观地讲，假设所有利润都等于1，那么在利润方面，您对选择的项目无动于衷，则只需要尽可能多的项目.贪婪算法会为您提供准确的信息.

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.

这篇关于所有利润等于1的背包问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！