0-1

大二算法设计实验源码

#include<iostream.h>
#include<stdlib.h>

void Knapsack(int c,int n,int[],int[],int m[][20]);
void Traceback(int c,int n,int[],int[],int m[][20]);

void main()
{
	int c,n;
	int m[20][20];
	cout<<"请输入背包容量：";
	cin>>c;
	cout<<"请输入物品数：";
	cin>>n;
	int *w=new int[n+1];
	int *v=new int[n+1];
	int *x=new int[n+1];
	cout<<"请输入各物品重量："<<endl;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	cout<<"请输入各物品价值："<<endl;
	for(i=1;i<=n;i++)
		cin>>v[i];
	Knapsack(c,n,w,v,m);
	Traceback(c,n,w,x,m);
	cout<<"0-1向量为："<<endl;
	for(i=1;i<=n;i++)
		cout<<x[i]<<"  ";
	cout<<endl;
}
void Knapsack(int c,int n,int w[],int v[],int m[][20])
{
	int jMax=(w[n]-1)>c?c:(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--)
	{
		jMax=(w[i]-1)>c?c:(w[i]-1);
		for(j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];
		for(j=w[i];j<=c;j++)
			m[i][j]=m[i+1][j]>(m[i+1][j-w[i]]+v[i])?m[i+1][j]:(m[i+1][j-w[i]]+v[i]);
	}
	m[1][c]=m[2][c];
	if(c>=w[1])
		m[1][c]=(m[1][c]>m[2][c-w[1]]+v[1])?m[1][c]:(m[2][c-w[1]]+v[1]);
}
void Traceback(int c,int n,int w[],int x[],int m[][20])
{
	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;
}