スペース最適化された0/1ナップザック実装からのアイテムリストの再構成

Question

0/1ナップザック動的プログラミングアルゴリズムのスペース最適化は、ナップザック容量と等しいサイズの1次元アレイ（例えば、A）最初のi個のアイテムが考慮され、ナップザックの容量がwであれば、A [w]は合計値を表す、各反復iで（必要であれば）A [w]を単純に上書きする。 この最適化が使用されている場合、DPアルゴリズムの各反復でいくつかの追加情報を保存することで、選択したアイテムのリストを再構築する方法はありますか？例えば、ベルマンフォードアルゴリズムでは、同様の空間最適化を実施することができ、先行ポインタのリスト、すなわち最後のホップ（または、ソース/宛先指向アルゴリズムが書かれている）。

ここでは、ans [i] [j]が最初のi項目を考慮した合計値を示すような2-dベクトルansを構築する動的プログラミングを使用する0/1ナップザック問題のC++関数を示します。ナップザック容量j。提案された解決策と、一定の目標値について、関係アイテムのセットを得ることは事実上不可能であり、私の理解に

void knapsack(vector<int> v,vector<int>w,int cap){ 
//v[i]=value of item i-1 
//w[i]=weight of item i-1, cap=knapsack capacity 
//ans[i][j]=total value if considering 1st i items and capacity j 
vector <vector<int> > ans(v.size()+1,vector<int>(cap+1)); 

//value with 0 items is 0 
ans[0]=vector<int>(cap+1,0); 

//value with 0 capacity is 0 
for (uint i=1;i<v.size()+1;i++){ 
    ans[i][0]=0; 
} 

//dp 
for (uint i=1;i<v.size()+1;i++) { 
    for (int x=1;x<cap+1;x++) { 
     if (ans[i-1][x]>=ans[i-1][x-w[i-1]]+v[i-1]||x<w[i-1]) 
      ans[i][x]=ans[i-1][x]; 
     else { 
      ans[i][x]=ans[i-1][x-w[i-1]]+v[i-1]; 
     } 
    } 
} 
cout<<"Total value: "<<ans[v.size()][cap]<<endl; 

//reconstruction 
cout<<"Items to carry: \n"; 
for (uint i=v.size();i>0;i--) { 
    for (int x=cap;x>0;x--) { 
     if (ans[i][x]==ans[i-1][x]) //item i not in knapsack 
      break; 
     else if (ans[i][x]==ans[i-1][x-w[i-1]]+v[i-1]) { //item i in knapsack 
      cap-=w[i-1]; 
      cout<<i<<"("<<v[i-1]<<"), "; 
      break; 
     } 
    } 
} 
cout<<endl; 
} 

Answer 1

：私は逆のこのベクトルANSを横断することにより、選んだ項目を再構築します。項目のセットは、廃棄された行を再度生成するか、または適切な補助データ構造を維持することによって得ることができる。これは、Aの各エントリを、それが生成されたアイテムのリストと関連付けることによって行うことができる。しかし、これは、最初に提案された解決策よりも多くのメモリを必要とする。ナップザック問題のバックトラッキングのアプローチは、thisジャーナルペーパーでも簡単に議論されています。