1

解決策を見つけることに成功せずに、与えられたタスクにほぼ 1 週間苦労しているので、このサイトが私の最後の希望です。

値と重量が異なる 20 個のアイテムを持つ0-1 ナップザック問題があり、サックの最大重量は 524 です。総重量が <= 524 で最大値が選ばれたアイテム。

それがどのように機能するかを分析するために、私を指摘するか、詳細な実装を提供してください!! どうもありがとうございました

4

1 に答える 1

6

強引なアイデアは簡単です：

  1. 20個のアイテムの可能なすべてのサブセットを生成し、重量の制約を満たすものだけを保存します。派手になりたい場合は、重みの制約に違反せずに他に何も追加できないサブセットのみを検討することもできます。これは、これらだけが正しい答えになる可能性があるためです。O（2 ^ n）
  2. 最大の重みを持つサブセットを見つけます。候補の数に関して線形であり、O（2 ^ n）の候補があるため、これはO（2 ^ n）です。

擬似コードが必要な場合はコメントしてください。

編集：ちょっと、これが念のための擬似コードです。

  GetCandidateSubsets(items[1..N], buffer, maxw)
  1. addedSomething = false
  2. for i = 1 to N do
  3.    if not buffer.contains(item[i]) and
           weight(buffer) + weight(items[i]) <= maxw then
  4.       add items[i] to buffer
  5.       GetCandidateSubsets(items[1..N], buffer)
  6.       remove items[i] from buffer
  7.       addedSomething = true
  8. if not addedSomething then
  9.    emit & store buffer

総当たり攻撃の実装であっても、GetCandidateSubsets関数はあまり効率的ではないことに注意してください。それを指摘してくれたamitに感謝します。これをやり直して、最初のパスの最適化として、順列ではなく、アイテムセットの組み合わせのみをウォークすることができます。

  GetMaximalCandidate(candidates[1..M])
  1. if M = 0 then return Null
  2. else then
  3.    maxel = candidates[1]
  4.    for i = 2 to M do
  5.       if weight(candidates[i]) > weight(maxel) then
  6.          maxel = candidates[i]
  7.    return maxel
于 2011-10-31T14:08:34.160 に答える