ナップザックの問題を段階的に計算する方法はありますか？任意の近似アルゴリズムですか？私は次のシナリオで問題を解決しようとしています。インクリメンタルにナップザックを計算する
Dを順序付けられていないデータセットとし、そうであってはいけません。 Dは3つのサブセット、すなわちD1、D2、D3に分割される。 D1、D2、およびD3は、必要に応じてそれぞれ注文することができます。私はセット（D1、D2）と（D2、D3）のための別々のナップザック解を計算したいが、D2を2回計算することは避けたい。だから、基本的に、私がしたい：
D2を介してデータトラバーサルを一度だけ実行される方法のためのナップザック結果を得ます。このような段階的にナップザックを解決する方法はありますか？
ウィキペディアが0/1ナップザックのために、この擬似コードを与える：https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do:
m[0, j] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i-1] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])
これはm[n, W]は（最後の行の最後の要素）ソリューションであるように、2次元配列のビルド - あなたはD2でこれを実行します。
は、その後、入力として、この配列を取り、
for i from D2.count+1 to (D2.count + other.count) do:行いませ初期化するfor j ...一部を行わない別のアルゴリズムを記述します。 （あなたはwとvの配列を調べるときにiを調整する必要があります）
0,1のナップザック問題を意味するとします。通常のDP解をD2単独で実行する場合、メモされた部分結果は、（D2、D1）または（D2、D3）のいずれかのDP解をブートストラップするのに適している。両方のソリューションを計算するには、D2のみの計算から部分的な結果のコピーを作成する必要があります。私はすぐに、ナップザック問題の他の変種に答える準備ができていません。 –
ありがとうございました。はい、0/1のナップザック問題です。私が知る限り、（D2、D1）の組み合わせがソートされていない場合、DPの2つのソリューションを組み合わせることは効率的ではありません。私の場合、D1とD2は別々にソートされ、集合S =（D2 U D1）またはS =（D2 U D3）は必ずしもソートされない。 –
「ソートされた」とは何を意味するのかよく分かりません。 DP @ JohnBollingerは要素の順序を気にしないので、ソートする必要はありません.D2の要素を前面に移動するだけで済みます。 –