Typical DP Contest H:ナップザック
解法
物を色ごとにグループ分けした.
dp[i][j]:i種類以下の色を使って,j以下の重さまで許容するときの価値の最大値.
としてdpした.
適当にやったらうまくdp出来ない状況に陥ったので,さらに適当にやりまくったらなんかちゃんと書けた.
コード
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>P; vector<P>V[50]; int N,W,C; int dp[51][10001]; 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);c--; V[c].push_back(P(w,v)); } for(int i=0;i<50;i++){ for(int j=C;j>0;j--){ int dp2[10001]={0}; for(int k=0;k<V[i].size();k++){ int w=V[i][k].first,v=V[i][k].second; for(int l=W;l>=0;l--){ int val=max(dp2[l],dp[j-1][l]); if(l-w>=0)val=max(val,max(dp[j-1][l-w]+v,dp2[l-w]+v)); dp2[l]=max(dp2[l],val); } } for(int k=0;k<=W;k++)dp[j][k]=max(dp[j][k],dp2[k]); } } cout<<dp[C][W]<<endl; return 0; }