编辑代码

#include<iostream>
#include <algorithm>
using namespace std;
 
 //数组第一个元素不用 
int w[6]={0,6,5,4,2,1}; //商品的体积2、3、4、5
int v[6]={0,5,3,5,3,2};	//商品的价值3、4、5、6
int bagV=8;	            //背包大小
int dp[5][9]={ {0} };	//动态规划表
int item[5];		    //最优解情况
 
void findMax() 
{//动态规划
	for(int i=1;i<=4;i++)
	 {
		for(int j=1;j<=bagV;j++)
		 {
			if(j<w[i])
				dp[i][j]=dp[i-1][j];
			else
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
		}
	}
}
 
void findWhat(int i,int j)
{//最优解情况
	if (i>=0)
	{
		if(dp[i][j]==dp[i-1][j])
		{
			item[i]=0;
			findWhat(i-1,j);
		}
		else if (j-w[i]>=0&&dp[i][j]==dp[i-1][j-w[i]]+v[i])
		{
			item[i]=1;
			findWhat(i-1,j-w[i]);
		}
	}
}
 
void print()
{
	for(int i=0;i<5;i++)
	{	//动态规划表输出
		for (int j=0;j<9;j++)
		{
			cout<<dp[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;
 cout<<"最优解为："; 
	for (int i=0;i<5;i++)
		cout<<item[i]<<' ';
cout<<"(按顺序表示各个物品的数量)";
	cout<<endl;
}
 
int main()
{
	findMax();
	findWhat(4,8);
	cout<<"动态规划表格为：\n"; 
	print();
 
	return 0;
}