exp3.cpp

著名的0-1背包问题 C++实现 矩阵显示过程

#include <iostream>
#define maxi 100
using namespace std;
int max(int a,int b)
{
	int temp;
	if (a<b)
	{
		temp=a;
		a=b;
		b=temp;
	}
	return a;
}
int knapsack01(int n,int c,int v[],int w[])
{
	int s[maxi][maxi],x[maxi],b,i,j;
	for(i=0;i<=n;i++)
		s[i][0]=0;
	cout<<"  0┃  "<<s[0][0];
	for(j=1;j<=c;j++)
	{
    	s[0][j]=0;
		cout<<"    "<<s[0][j];
	}
	cout<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"  "<<i<<"┃  "<<s[i][0]; 
		for(j=1;j<=c;j++)
		{
			s[i][j]=s[i-1][j];
			if(j>=w[i])
				s[i][j]=max(s[i-1][j],v[i]+s[i-1][j-w[i]]);
			if(s[i][j-1]<10)
				cout<<"    "<<s[i][j];
			else cout<<"   "<<s[i][j];
		}
		cout<<endl;
	}
	b=s[n][c];
	cout<<"放入背包的最优解过程："<<endl;
	for(i=n;i>=1;i--)
	{
		if(s[i][c]==s[i-1][c])
			x[i]=0;
		else
		{
			x[i]=1;
			c=c-w[i];
		}
		cout<<"x["<<i<<"]="<<x[i]<<' ';
	}
	cout<<endl;
	s[n][c]=b;
	return s[n][c];
}
int main()
{
	int wi,vi,w[50],val[50],C,number;
	cout<<"请输入背包的容量：c=";
	cin>>C;
	cout<<"请输入物品的数量：n=";
	cin>>number;
	for(int i=1;i<=number;i++)
	{
		cout<<"请输入物品 "<<i<<" 的体积和价值"<<endl;
		cout<<"体积：";
		cin>>wi;
		cout<<"价值：";
	    cin>>vi;
		w[i]=wi;
		val[i]=vi;
	}
	cout<<"   ┃   0    1    2    3    4    5    6    7    8    9"<<endl;
	cout<<" ━╂━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;
	cout<<"背包所能装入的最大价值为："<<knapsack01(number,C,val,w)<<endl;
	return 0;
}