0-1バックパックは一次元配列を使用しています.

ローリング配列を使って空間を2*Vに最適化し、リュックサック9の話では1次元配列を使っても同様の効果を達成できると述べています.個人的にはこれもローリング思想の一つであり、1次元配列解1を使ってバックパックを何度も使うことができるので、完全リュックサックの最適化の現実的な方法も1次元配列を使用するので、この方法を理解する必要があります.
一次元配列f[0...v]だけを使用すれば、私たちが達成する効果は、第iのループが終了した後のf[v]で表されるのは、二次元配列を使用した時のf[i]、[v]であり、前iの物体が容量vに直面した時の最大値である.f[v]は二つの状態から来ていると知っています.f[i-1]、[v-c[i]は一次元配列を使っていますが、i番目のサイクルの前にf[v]は実際f[i-1]、[v]です.では、第二のサブ問題の値はどうやって得られますか?実際、毎回のサイクルでv=v...0の順にf[v]を押すと、f[v-c[i]がf[i-1]、[v-c[i]の状態で保存されていることが保証されます.状態移行方程式は以下の通りです.
1
v=V…0f(v)=max｛f(v),f(v-c[i])+w[i]｝
二次元配列の状態遷移方程式と比較できます.
1
f(i,v)=max｛f(i-1,v)f(i-1,v-c[i])＋w[i]｝
上記のように、f[v-c[i]は元のf[i-1][v-c[i]の状態に相当します.vの循環順を逆順に変えると、01のバックパックではなく、完全リュックサックになります.ここで一つの例を挙げてみます.なぜ順番が01リュックではないのか分かります.
もし物体z容量が2あるとしたら、価値vzが大きく、バックパックの容量が5であり、vの循環順が逆順でない場合、外層が物体zに循環して走る場合、v=2に物体zがリュックサックに入れられ、v=4になると最大値を求めて、物体zがリュックサックに入れます.物体zを一度入れました.そうすると、この物体はリュックサックに二回入れられます.要求に合わないです.逆順にvを循環すれば、この問題は解決されます.
コードは、理解を深めるために、ループ終了出力の各状態をテキストに含めることができます.二次元配列を使用したときの状態遷移行列と同じです.

#include
using namespace std;
 
 
int maxV[201];    
int weight[11];
int value[11];
int V, N;
 
void main()
{
    int i, j;
    scanf("%d %d",&V,&N);
    for(i = 0; i < N;++i)
    {
       scanf("%d%d",&weight[i],&value[i]);
    }
 
   
    for(i = 0; i < N;++i)
    {
      
       for(j = V; j >= weight[i]; --j) 
       {
           int tmp =maxV[j-weight[i]]+value[i];
           maxV[j] =(maxV[j] > tmp) ? maxV[j] : tmp;
       }
    }
   printf("%d",maxV[V]);
}

一次元配列を使ってコードが非常に簡潔であることが分かる.
===========================================================================================