#include #include using namespace std; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //ダイナミック計画法 //ケースに最大の重さはmax_weightであるの最大の価値のものを入れる //const int MAX_N: 最大N //const int MAX_W: 重さは最大範囲値 //const vector &weight:重さの配列 //const vector &value:価値の配列 //const int max_weight: 入れられる最大の重さ //例:重さ 価値 // 5kg 20円 // 4kg 10円 // 3kg 12円 //最大10kgのケースに最大の価値を入れる //結果: 5kg[20]+3kg[12]=32円 //weight[]={5,4,3} //value[]={20,10,12} int DynamicPlanMethod(const int MAX_N,const int MAX_W,vector &weight,const vector &value,const int max_weight) { //ダイナミック計画法で解を求める // DPテーブル // dp[i][j]はi番目以降の品物から重さの和がj以下なるように選んだときの価値の和の最大値を表す。 vector> dp(MAX_N+1,vector(MAX_W+1)); for (int j = 0; j <= MAX_W; j++) { dp[MAX_N][j] = 0; } for (int i = MAX_N - 1; i >= 0; i--) { for (int j = 0; j <= max_weight; j++) { if (j < weight[i]){ dp[i][j] = dp[i + 1][j]; }else{ dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - weight[i]] + value[i]); } } } return dp[0][max_weight]; } int main(int argc, char* argv[]) { int N,K; cin>>N>>K; const int MAX_N=N; const int MAX_W=K; int max_weight=K; int i; vector weight(MAX_N); vector value(MAX_N); for (i=0;i>weight[i]; value[i]=weight[i]; } int w= DynamicPlanMethod(MAX_N,MAX_W,weight,value,max_weight); cout<