裏紙

ほぼ競プロ、たまに日記

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]);
}