蓝桥杯 01背包 动态规划

 当i<0时           maxValue =0 
 其他情况	   maxValue = max(getMax(bagWeight-w[i],i-1)+v[i] ,getMax(bagWeight,i-1));	AC代码如下，
int weight[MAX_W][MAX_N] 数组 便是  dp[i][j]
#include<iostream>#include<cstdlib>#include<malloc.h>#include<algorithm>#include <memory.h>using namespace std;#define MAX_N 201#define MAX_W 5001  int w[MAX_N];	//物体重量 int v[MAX_N];   //物体价值 int n;			//物体个数int m;			//背包的最大重量 int weight[MAX_W][MAX_N]; //weight[i][j] 表示背包为i重量产品数为j 的最高价值 int getMax(int bagWeight,int i){	int value;	if(i < 0) return 0;			//没有物品	if(weight[bagWeight][i] != -1){		value=weight[bagWeight][i];	//“备忘录”，此前保存的最大值	} else if(i==0){			// 最后一个物品		if(bagWeight >= w[i])return v[i];	//买			else return 0;				//买不起	} 	else if(i!=0 && bagWeight >= w[i]){		//动态规划		value = max(getMax(bagWeight-w[i],i-1)+v[i] ,getMax(bagWeight,i-1));	} else {					//同样买不起		value = getMax(bagWeight,i-1);			}	weight[bagWeight][i] = value;			//保存最大值	return value;					//返回最大值} int main(){//	freopen("2.txt","r",stdin);	memset(weight,-1,sizeof(weight));//	cout<< sizeof(weight);	int maxValue=0;	cin>>n>>m;	for(int i=0;i<n;i++)		cin>>w[i]>>v[i];	maxValue=getMax(m,n-1);		cout<<maxValue;	return 0; }