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

Question

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

我有一个容量固定的袋子，比如说C。我们有一份物品清单和它们的重量。所有物品的总重量都大于C。我如何才能在袋子里装下最大数量的物品（同时尽量装满袋子）？

我曾想过对清单进行排序并选择物品，直到袋子装满为止，但下面的例子反驳了的想法

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

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

这个问题可以通过将这个问题转化为背包来解决，每个物品的重量等于它的重量。还有其他算法吗？

Answer 1

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

我会-

• 生成所有可能的总和
• 按最大容量过滤总和（袋大小）
• 从生成的总和中获取最大总和
• 按最大和过滤和
• 按最大剩余项目数查找和筛选

这里有一个大家都喜欢的语言示例——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

Answer 2

根据您的评论，如果目标是让袋子尽可能满，那么问题就是背包问题，其值等于它们的重量。

使用维基百科中给出的动态编程技术来解决它。