0-1背包.cpp

3

#include<string>
#include<iomanip>
#include<iostream>
#include<fstream>
using namespace std;
#define M 50
void Knapsack(int v[M],int w[M],int c,int n,int m[M][M])
{
	void Traceback(int[M][M],int[M] ,int ,int ,int [M]);
	int jMax;
	if((w[n]-1)>=c)
		jMax=c;
		else
          jMax=w[n]-1;
	for(int j=0;j<=jMax;j++)
		m[n][j]=0;
	for( j=w[n];j<=c;j++)
		m[n][j]=v[n];
	for(int i=n-1;i>1;i--){
		if((w[i]-1)>=c)
		 jMax=c;
		else
          jMax=w[i]-1;
		for( j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];
		for(j=w[i];j<=c;j++)
			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];
	}
	m[1][c]=m[2][c];
	if(c>=w[1])
		if(m[1][c]<m[2][c-w[1]]+v[1])
		m[1][c]=m[2][c-w[1]]+v[1];
    int x[4];
		Traceback(m, w, c, n,x);
}
void Traceback(int m[M][M],int w[M],int c,int n,int x[M])// 寻找并标志最优解的解法
{
	for(int i=1;i<n;i++)
		if(m[i][c]==m[i+1][c])
			x[i]=0;
		else{
		x[i]=1;
		c-=w[i];}
		x[n]=(m[n][c])?1:0;
		cout<<"找到列表为";
		for(i=1;i<=n;i++)
			if(x[i]==1)
				cout<<"第"<<i<<"个--,";
}
int main(int argc, char* argv[])
{
	int v[M],w[M],c;
	int n,m[M][M];
	int i;
	char a;
	string str;
	cout<<"载入已有数据或手动输入(y)\(n):"<<endl;
	cin>>a;
	if(a=='y')
	{
	ifstream  fcin("test.txt");
	if(fcin.fail())
	   {
	  //file not found
	   cout<<"文件不能打开"<<endl;
	  return 1;
	   }
	fcin.seekg(0);
	fcin>>n;
	fcin>>c;
	for(i=1;i<=n;i++)
		fcin>>w[i];
	for(i=1;i<=n;i++)
		fcin>>v[i];
	Knapsack(v,w,c,n,m);
	}
	else if(a=='n'){
	cout<<"请输入规划的物品的数量n:"<<endl;
	cin>>n;
	cout<<"请输入背包的载重量c:"<<endl;
	cin>>c;
	cout<<"请输入物品重量序列w[]:"<<endl;
	for(i=1;i<=n;i++)
		cin>>w[i];
	cout<<"请输入物品价值序列v[]:"<<endl;
	for(i=1;i<=n;i++)
		cin>>v[i];
	Knapsack(v,w,c,n,m);
	}
	else
		cout<<"输入不正确，请重新输入."<<endl;
	return 0;
}