AOJ DPL1_C - Knapsack Problem
・問題
Knapsack Problem | Aizu Online Judge
前の問題から若干問題を変えて、1つの商品を何個でも入れることができるという制約に変わった。
・考え方
前の問題に倣い、
dp[i][j]:=品物1~iの中から選び、ナップサックの大きさがjの時に入れられる商品の価値合計の最大値
とすることにする。この状態に辿り着けるものを考えると、品物1~(i-1)に対して品物iを新たに追加することにする。そのときに、品物iをk(k>=0)個入れる。その時(j-k*w[i])のナップサックに品物iをk個入れる事になる。これより、
dp[i][j] = max(dp[ i-1 ][ j-k*w[i] ] + k*v[i] | (0<=k, j-k*w[i]>=0))
ナイーブに上のことを式にするとこうなる。ここから式変形していく。
- まず、k=0と1<=kに分離。
= max(dp[i-1][j], max(dp[ i-1 ][ j-k*w[i] ] + k*v[i] | (1<=k, j-k*w[i]>=0)) )
- 次に、t+1=kとおく。
= max(dp[i-1][j], max(dp[ i-1 ][ j-(t+1)*w[i] ] + (t+1)*v[i] | (1<=(t+1), j-(t+1)*w[i]>=0)) )
= max(dp[i-1][j], max(dp[ i-1 ][ j-w[i]-t*w[i] ] + t*v[i] + v[i] | (0<=t, j-w[i]-t*w[i]>=0)) )
- そして、j-w[i]=pとおく。
= max(dp[i-1][j], max(dp[ i-1 ][ p-t*w[i] ] + t*v[i] + v[i] | (0<=t, p-t*w[i]>=0)) )
- 定数v[i]はmaxの外に出しても変数tには無関係なので問題ない。
= max(dp[i-1][j], max(dp[ i-1 ][ p-t*w[i] ] + t*v[i] | (0<=t, p-t*w[i]>=0)) + v[i] )
- ここで、真ん中のmaxの中身が、一番最初のmaxの中身と同じになっていることに気づく!!!!(jがpに変わっている形)
=max(dp[i-1][j], dp[i][p] + v[i])
=max(dp[i-1][j], dp[i][j-w[i]] + v[i])
これでO(NW)で回せる。ちなみに、実装では商品情報のvとwに関しては0オーダーで入力してるの2つindexはi->i-1にして実装した。
・感想
これも蟻本で読んだので思いつけたが、こんな式変形どうやって思いつくのだろうか...と思ったけど、この式変形ってなんか大学受験の数学っぽいなって思ったし、そういう感覚は大事かも。とりあえず3問やって感じたことがある:
状態を列挙し、
そこにたどり着く状態はどこから来るのかを漏れ無く考え、
漸化式を立てる。そして、その漸化式の方向にそってループをまわす
この3ステップを紙にがしがし書きながら進めば、なんとなく行けそうな気がしてきた。そもそもdpテーブルをどういう風に持たせるかでもう決まってくるようなものだ。だから慣れが大事と言われているのかもしれない。まああと漸化式が立てられるかも割と問題な気がする。
・実装(C++)
#include <algorithm> #include <cstdio> #include <iostream> using namespace std; int main(){ int N,W; int v[100],w[100]; //input scanf(" %d %d", &N, &W); for(int i=0; i<N; ++i) scanf(" %d %d", &v[i], &w[i]); //solve //dp[i][j]:=品物1~iの中から選び、ナップサックの大きさがjの時に入れられる商品の価値合計の最大値 int dp[101][10001]={0}; for(int i=0; i<N; ++i){ for(int j=0; j<=W; ++j){ if(j-w[i]>=0) dp[i+1][j] = max( dp[i+1][j-w[i]]+v[i], dp[i][j] ); else dp[i+1][j] = dp[i][j]; } } printf("%d\n", dp[N][W]); }