编辑代码

#include <iostream>
#include <cmath>
using namespace std;
#define n 5		     //物品数量
#define max_w 10	           //背包最大重量
int value[n]={5,3,5,3,2};      //物品价值
int weight[n]={6,5,4,2,1};     //物品重量
 
int max(int a,int b){
	if(a>b) return a;
	else return b;
}

int beibao01(int *x) 
{
	int i,j;
	int dpt[n][max_w+1]={0};  //动态规划表
	int max_v;                //最大价值
	int real_w;               //当前重量
 
	for (j = 0; j <= max_w; j++)
		if(j >= weight[0])
			dpt[0][j] = value[0];
	for (i = 1; i < n; i++) 
	{
		for (j = 1; j <= max_w; j++)
		{
			if (j < weight[i])
				dpt[i][j] = dpt[i-1][j];
			else
			{
				dpt[i][j] = max(dpt[i-1][j], dpt[i-1][j-weight[i]] + value[i]);
			}
		}
	}
	for (j = 1; j <= max_w; j++)
	{
		if(dpt[n-1][j] > max_v)
		{
			max_v = dpt[n-1][j];
			real_w = j;
		}
	}
	for (i = n-1; i > 0; i--) 
	{
		if(dpt[i][real_w ] != dpt[i-1][real_w ])
		{
			x[i] = 1;
			real_w = real_w-weight[i];
		}
	}
	if(real_w != 0) 
		x[0] = 1;
	return max_v;
}
 
int main()
{
	int x[n]={0};
	cout<<"最大的价值为："<<beibao01(x)<<endl;
}