AtCoder Beginner Contest 015 D - 高橋くんの苦悩

問題

atcoder.jp

問題概要

ナップサック問題に言い換える。

品物がN個ありi番目(1-index)の重さはA[i-1]、価値はB[i-1]である。
重さがWを超えず、個数がKを超えないように選ぶとき、価値の合計の最大値を求めよ。

解法

個数制限がない場合は普通のナップサック問題なので以下の記事の方法で解けばいい。
greentomatotan.hatenadiary.jp

この場合は個数制限があるので添え字を増やす。

dp[i][j][k] : i番目(1-index)の品物まで見て重さがjを超えないように、個数がkを超えないように選ぶときの価値の合計の最大値。
0≦i≦N、0≦j≦W、0≦k≦K

i番目の品物を選ぶか選ばないかの2通りがある。

i番目の品物を選ばないとき
dp[i][j][k]=dp[i-1][j][k]

i番目の品物を選ぶとき
dp[i][j][k]=dp[i-1][j-A[i-1]][k-1]+B[i-1]

これらのうちの大きい方となる。
ただしj-A[i-1]<0またはk-1<0の時は配列外参照となるため
dp[i][j][k]=dp[i-1][j][k]となる。

i=0の時は何も選ばないのでdp[i][j][k]=0となる。

ソースコード

signed main() {
	int W, N, K;
	cin >> W >> N >> K;
	vector<int>A(N);
	vector<int>B(N);
	rep(i, N) {
		cin >> A[i] >> B[i];
	}
	vector<vector<vector<int>>>dp(N + 1, vector<vector<int>>(W + 1, vector<int>(K + 1)));
	rep(i, N + 1) {
		rep(j, W + 1) {
			rep(k, K + 1) {
				if (i == 0) {
					dp[i][j][k] = 0;
				}
				else {
					if (j - A[i - 1] < 0 || k - 1 < 0) {
						dp[i][j][k] = dp[i - 1][j][k];
					}
					else {
						dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - A[i - 1]][k - 1] + B[i - 1]);
					}
				}
			}
		}
	}
	cout << dp[N][W][K] << endl;
}