ダイナミックプランニング(三)リュックサック問題

問題の説明
n個の品物があり、それぞれの品物は1個しかありません.物品iの体積はv[i]、重量はw[i]である.リュックサックの体積はCで、どのようにリュックサックの中に入れることができる物品を積むのが最も重いことを求めますか?
構想分析
0-1バックパック問題と呼ぶのは、すべてのアイテムが1つしかないため、選択アイテムがバックパックに積まれる場合、積まないか積まないか、コンピュータの0(FALSE)と1(TRUE)の概念に対応する2つの選択肢しかないからです.我々はdp[i][j]で「前のi個の品物を体積jのリュックサックの中の最大総重量に入れる」ことを表す.ステータス遷移方程式:

dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);

のうち、dp[i-1][j]は、荷物iをリュックサックに積まないことを示すので、リュックサックの重量は前のi-1個の重量である.後者のdp[i-1][j-v[i]+w[i]は、i番目の物品をリュックサックに積む場合、最適サブ問題によって得られなければならないため、iを積まない前の重量も必ず最大であることを示す.
ループ時,この遷移方程式は2次元配列であり,i行目はi−1行目の値に依存することを見出したので,初期化時には0行目をすべて0にすればよい,すなわちdp[0][j]=0である.
コードの例

for(int j = 0; j <= C; ++ j) {
	dp[0][j] = 0;
}

for(int i = 1; i <= n; ++ i) {
	scanf("%d %d", &v, &w);
	for (int j = 0; j <= C; ++ j) {
		if(j >= v) {
			dp[i][j] = max(dp[i-1][j], dp[i-1][j - v] + w);
		} else {
			dp[i][j] = dp[i-1][j];
		}
	}
}

dp[i][j]は「前のi個の物品を体積jのリュックサックに入れる最大総重量」を表す.したがって、外循環iは、前の1つの物品から前のn個の物品までを表し、内循環jは、体積が0から最大のCまでを表す.データは同じように計算されるので、事前にすべてのデータを読む必要もなく、保存する必要もありません.
スクロール配列
さらに奇妙なことに、配列dpを1次元プログラミングすることができます.ここでは非常に精巧で偶然ですが、これはプログラムコードの最適化にすぎません.0-1リュックサックの問題が1次元リュックサックの問題ではありません.

memset(dp, 0, sizeof(dp)); 
for (int i = 1; i <= n; ++ i) {
	scanf("%d%d", &v, &w);
	for(int j = C; j >= v; j --) {
		dp[j] = max(dp[j], dp[j-v] + w);
	}
}

スクロール配列を採用する場合、f[i][j]の値はf[i-1][j]であるか、f[i-1][j-v]+wであるかのいずれかである.jは右から左に計算するので、現在f[j]にはf[i-1][j]が保存されていますが、f[j-v]にはf[i-1][j-v]の値が保存されているので、ちょうどいいです.このようにすれば、私たちは多くの空間の代価を節約することができます. 
注意内ループjはvになると停止するので,j>=vは常に成立するため,jとvの関係を判断する必要はない.jリュックサックは満タンでなければなりません
また、テーマが要求され、リュックサックがいっぱいにならなければならない場合は、初期化の条件を変更するだけでいいです.

memset(dp, -0x3f3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; ++ i) {
	scanf("%d%d", &v, &w);
	for(int j = C; j >= v; -- j) {
		dp[j] = max(dp[j], dp[j-v] + w);
	}
}

リュックサック九講では、初期化の過程、実際には、一つのものがないときの解を説明しています.だからリュックサックをいっぱい詰めなければならないなら、dp[0]という解しかありません.つまり、価値が0のものを、容量が0のバッグにぴったり入れます.その他はすべて不正解なので負∞に初期化してください.リュックサックを必ず満タンにする必要がない場合、すべての解は正しい解であるため、0に初期化することができる.
リュックサックの問題を繰り返すことができます
繰り返し可能なリュックサックは、0-1リュックサックではなく、1つのアイテムの個数が無限であるということです.同様に、状態遷移方程式があります.

dp[i][v]=max{ dp[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v }

つまり、この品物は0回、1回、2回...v/c[i]回、入れられないことを知るまで.
しかし、O(NV)の複雑さの最適化もあり、コードは簡単で、上のスクロール配列が0-1リュックを実現し、内循環jが逆転すればよい.原理は不明ですが、私のレベルが低すぎるのか、今のところ理解できません.
疑似コードは次のとおりです.

procedure CompletePack(cost,weight)
    for v=cost..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

参考資料

『アルゴリズムコンテスト入門経典』&『訓練マニュアル』劉汝佳

リュックサック九講

刷題の博文