01バックパックの問題(ダイナミックプランニング)
835 ワード
以下のコードのp[i][j]の意味は、リュックサック容量がjの場合、前のi個の物品を入れる最大の価値である.i番目の品物が入らないweight[i]>jであれば、p[i][j]=p[i-1][j],2.weight[i]<=jであれば、p[i][j]=max(p[i-1][j],p[i-1][j-weight[i]++value[i])は、「i番目を入れない」とi番目を入れる最大値である.サイクルを経て、最後に欲しい結果を得る.
#include
#include
using namespace std;
vector weight;
vector value;
int main(){
int n;
cin>>n;
int w,v;
weight.push_back(0);
value.push_back(0);
for(int i=1;i<=n;i++){
cin>>w>>v;
weight.push_back(w);
value.push_back(v);
}
int maxWeight;
cin>>maxWeight;
int **p=new int*[n+1];
for(int i=0;ij){
p[i][j]=p[i-1][j];
}else{
p[i][j]=max(p[i-1][j],p[i-1][j-weight[i]]+value[i]);
}
}
}
cout<