0-1背包问题.cpp

0-1背包问题,采用了求最优解和求最优值,分别用递归和回代来实现.

#include <fstream.h>
#include <iostream.h>
#include<iomanip.h>
#include<string.h>
int min(int w,int c)
{
	int temp;
	if (w<c)     temp=w;
	else        temp=c;
	return temp;
}
int max(int w,int c)
{
	int temp;
	if (w>c)      temp=w;
	else         temp=c;
	return temp;
}
void knapsack(int v[],int w[],int c,int n,int**m)      //求最优值
{
	int jmax=min(w[n]-1,c);
	for(int j=0;j<=jmax;j++)
		m[n][j]=0;
	for(int jj=w[n];jj<=c;jj++)
		m[n][jj]=v[n];
	for(int i=n-1;i>1;i--)                       //递归部分
	{                           
		jmax=min(w[i]-1,c);
		for(int j=0;j<=jmax;j++)
			m[i][j]=m[i+1][j];
		for(int jj=w[i];jj<=c;jj++)
			m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);
	}
	m[1][c]=m[2][c];
	if(c>=w[1])
		m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
	cout<<"最优值："<<m[1][c]<<endl;
	for(int l=2;l<=n;l++)
		for(int j=0;j<=c;j++)
		{
			cout<<m[l][j]<<setw(c-1);
		}    
		cout<<endl;
}
int traceback(int **m,int w[],int c,int n,int x[])      //回代，求最优解
{
	ofstream cout("output.txt");
    cout<<"得到的一组最优解如下:"<<endl;
	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;
		for(int y=1;y<=n;y++)
		{
			cout<<setw(4)<<x[y];
		}
		return x[n];
}
void main()
{
	ifstream cin("input.txt",ios::nocreate);
	if(!cin.fail())
	{
	ofstream cout("output.txt");
	int n,c;
	int **m;
	cin>>n>>c;
	int *v=new int[n+1];
	for(int i=1;i<=n;i++)
		cin>>v[i];
	int *w=new int[n+1];
	for(int j=1;j<=n;j++)
		cin>>w[j];
	int *x=new int[n+1];
	m=new int*[n+1];             //动态的分配二维数组
	for(int p=0;p<n+1;p++)
	{
		m[p]=new int[c+1];
	} 
	knapsack(v,w,c,n,m);
	traceback(m,w,c,n,x);
	}
}