编辑代码

#include <iostream>    //w 重量 v价值  c容量  n物品数
using namespace std; 
void knapsack(int w[],int v[],int c,int n)
{
	int bag[100]={0};
	int m[100][100]={0};
	int i=0;
	int j=0;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=c;j++)
		{
			if(i==0)
				m[i][j]=0;
			else if(j>=w[i])  //装的进
			{
				if(m[i-1][j]>m[i-1][j-w[i]]+v[i])   //不装  价值大
				{
					m[i][j]=m[i-1][j];
				}
				else
				{
					m[i][j]=m[i-1][j-w[i]]+v[i];   //装  价值大
				}
			}
			else if(j>=0&&j<=w[i])   //装不进
				m[i][j]=m[i-1][j];
		}
	}
	j=c;
	for(i=1;i<=n;i++)        //查找哪些物品装入背包
	{
		if(m[i][j]==m[i-1][j])  //不装
			bag[i]=0;
		else
		{
			bag[i]=1;    //装
			j=j-w[i];    //没装之前重量
		}
	}
	cout<<"背包的最大价值为：1"<<m[n][c]<<endl;
	cout<<"0-1背包：";
	for(int k=1;k<=n;k++)
		cout<<bag[k]<<" ";
	cout<<endl;
}
int main()
{
	int n=0;
	int c=0;
	int w[100]={0};
	int v[100]={0};
	int k=1;
	cout<<"请输入物品的个数："<<endl;
	cin>>n;
	cout<<"请输入每个物品的重量："<<endl;
	for(k=1;k<=n;k++)
		cin>>w[k];
	cout<<"请输入每个物品的价值："<<endl;
	for(k=1;k<=n;k++)
		cin>>v[k];
	cout<<"请输入背包的容量："<<endl;
	cin>>c;
	knapsack(w,v,c,n);
	return 0;
}