17

複数の制約がある場合（たとえば、各アイテムの体積と重量が関連していない、体積制限と重量制限の両方）、多重制約ナップサック問題、多次元ナップサック問題、またはmが得られます。 -次元ナップサック問題。

これを最も最適化された方法でコーディングするにはどうすればよいですか？さて、ブルートフォース再帰ソリューションを開発することができます。分枝限定法かもしれませんが、ある種のメモ化を行うか、うまく行かないと大量のメモリを消費する動的計画法を使用するまでは、ほとんどの場合、本質的に指数関数的です。

私が直面している問題はこれです

両方に上限があるため、一般的なKnapSack（Capacity、i）の代わりにknapsack関数KnapSack（Capacity、Value、i）を使用しています。誰かがこれで私を導くことができますか？または、適度に大きいnのこれらの問題を解決するための適切なリソースを提供します

または、このNPは完全ですか？

ありがとう

4

5 に答える 5

6

制約をマージします。http://www.diku.dk/~pisinger/95-1.pdf の 1.3.1 章の「制約のマージ」を参照して ください。

例として
、 variable 、 constraint1 、 constraint2
1 、 43 、 66
2 、 65 、 54
3 、 34 、 49
4 、 99 、 32
5 、 2 、 88 があるとし ます。

最初の制約に大きな数を掛けてから、2 番目の制約に追加します。

したがって
、変数、マージされた制約
1 、430066
2 、650054
3 、340049
4 、990032
5 、20088 があります。

そこから、1 つの制約でやりたいアルゴリズムを実行します。これで頭に浮かぶ主なリミッターは、変数が保持できる桁数です。

于 2014-02-05T03:16:01.877 に答える
4

良い例として、次の問題に役立ちます。

正の重みと N 個の頂点を持つ無向グラフ G が与えられます。

あなたはMのお金の合計を持つことから始めます。頂点 i を通過するには、S[i] のお金を支払わなければなりません。十分なお金がなければ、その頂点を通過できません。上記の条件を考慮して、頂点 1 から頂点 N への最短経路を見つけます。または、そのようなパスは存在しないと述べます。同じ長さのパスが複数存在する場合は、最も安いパスを出力します。制限: 1

擬似コード:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.
于 2009-12-16T06:36:36.037 に答える
2

複数の制約があるナップザックはパッキングの問題です。読んでください。 http://en.wikipedia.org/wiki/Packing_problem

于 2009-12-01T18:06:12.290 に答える
-3

あなたが言ったように、vol と weight はどちらも正の量です。重みが常に減少するという事実を使用してみてください。

knap[position][vol][t]

が正のときt=0、負のときです。wtt=1wt

于 2016-08-21T18:06:42.533 に答える