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<