Typical DP Contest H - ナップザック

問題文 : ナップザック

解法 :

色ごとのナップサックを行なって, その結果をmerge していく(すでに$K$ 色使われたナップサックテーブル上で新たな色を追加することでできるのが$K+1$ 色でのナップサックテーブルとなっていることを利用する.)

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

int N, W, C;
int dp[51][100001];
int dp2[51][100001];
vector<pair<int, int> > item[50];

int main()
{
	scanf("%d %d %d", &N, &W, &C);
	
	for (int i = 0; i < N; i++){
		int w, v, c;
		scanf("%d %d %d", &w, &v, &c);
		item[--c].push_back(make_pair(w, v));
	}
	
	for (int i = 0; i < 50; i++){
		memcpy(dp2, dp, sizeof(dp));
		for (int l = C - 1; l >= 0; l--){
			for (int j = 0; j < item[i].size(); j++){
				for (int k = W; k - item[i][j].first >= 0; k--){
					dp2[l][k] = max(dp2[l][k], dp2[l][k - item[i][j].first] + item[i][j].second);
				}
			}
		}
		for (int l = C - 1; l >= 0; l--){
			for (int j = 0; j <= W; j++){
				dp[l + 1][j] = max(dp[l + 1][j], dp2[l][j]);
			}
		}
	}
	
	printf("%d\n", dp[C][W]);
	
	return (0);
}