1

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

我有一个容量固定的袋子，比如说 C。我们有一个物品清单及其重量。所有物品的总重量大于 C。我怎样才能在袋子中装下最大数量的物品（也尽量装满袋子）？

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

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

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

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

4

2 回答 2

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
于 2013-11-23T05:30:43.267 回答
1

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

使用Wikipedia中给出的动态编程技术解决它。

于 2013-11-23T05:43:22.953 回答