algorithm - 如何选择加权项目以实现利润最大化？

Question

这听起来像是一个简单的问题，但我无法找到好的解决方案。该问题类似于背包问题，但略有修改。

我有一个固定容量的包，比如 C。我们有一个元素 list 及其重量。所有元素的总重量都大于C，我怎样才能把最大数量的元素装进包里(也尽量装满包)？

我想对列表进行排序并选择项目，直到袋子装满，但下面的例子反驳了这个想法

C = 100 和L = 50, 40, 20, 30。

当我排序时，我得到 20、30、40、50，因此我的分配将是 (20+30+40) = 90。但我们可以获得更好的组合 (20+30+50) = 100。

通过赋予每个元素与其重量相等的重量，将此问题转化为背包问题即可解决该问题。还有其他算法吗？

Answer 1

免责声明:这不是最有效的解决方案；然而，这是解决方案。

我愿意——

• 生成所有可能的和
• 按最大容量(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