这听起来像是一个简单的问题,但我无法找到好的解决方案。该问题类似于背包问题,但略有修改。
我有一个固定容量的包,比如 C。我们有一个元素 list 及其重量。所有元素的总重量都大于C,我怎样才能把最大数量的元素装进包里(也尽量装满包)?
我想对列表进行排序并选择项目,直到袋子装满,但下面的例子反驳了这个想法
C = 100 和 L = 50, 40, 20, 30。
当我排序时,我得到 20、30、40、50,因此我的分配将是 (20+30+40) = 90。但我们可以获得更好的组合 (20+30+50) = 100。
通过赋予每个元素与其重量相等的重量,将此问题转化为背包问题即可解决该问题。还有其他算法吗?
最佳答案
免责声明:这不是最有效的解决方案;然而,这是解决方案。
我愿意——
- 生成所有可能的和
- 按最大容量(bagSize)过滤总和
- 从生成的总和中获取最大总和
- 按最大总和过滤总和
- 根据剩余的最大项目数查找和过滤
这是一个用每个人都喜欢的语言 - Haskell 编写的示例!
import Data.List
knappsack bagSize items = answers
where
sums = [(xs, sum xs) | xs <- subsequences items]
sumFilter = filter ((<= bagSize) . snd) sums
maxSum = foldl max 0 . map (sum . fst) $ sumFilter
maxFilter = filter ((== maxSum) . snd) sumFilter
maxLen = foldl max 0 . map (length . fst) $ maxFilter
lenFilter = filter ((== maxLen) . length . fst) maxFilter
answers = lenFilter
关于algorithm - 如何选择加权项目以实现利润最大化?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20158661/