编辑代码

#include <iostream>
#include <algorithm>//max()函数头文件 
#include <cstring>//memset函数头文件 
using namespace std;
#define N 100

int main(){
	int dp[N][N];
	memset(dp,0,sizeof(dp)); 
	int n=5;//共五件物品 
	int BagMax=10;
	cout<<"输入背包容量："<<BagMax<<endl;
	
	int height[N]={6,5,4,2,1};int value[N]={5,3,5,3,2};//物品重量数组，物品价值数组 
	int MaxValue=0;
	cout<<"物品重量: "<<height[0]<<" "<<height[1]<<" "<<height[2]<<" "<<height[3]<<" "<<height[4]<<endl;
	cout<<"物品价值: "<<value[0]<<" "<<value[1]<<" "<<value[2]<<" "<<value[3]<<" "<<value[4]<<endl;
	
	for(int i=1;i<=n;i++){//仅对i个物品选择  
		for(int j=0;j<=BagMax;j++){//穷尽背包空间 
			dp[i][j]=dp[i-1][j];//初始化
			if(height[i]<=j){//第i个物品重量在背包可容纳范围内 
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-height[i]]+value[i]);
				if(dp[i][j]>MaxValue){MaxValue=dp[i][j];} 
			} 
		}
	} 
	
	cout<<"背包装的物品最大价值："<<MaxValue<<endl;
	return 0;
}