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 に答える