main.cpp

0-1背包问题

#include <iostream.h>
#include <math.h>
#include <malloc.h>
#define MAXCOUNT 100
#define MAXWEIGTH 200
int c[MAXCOUNT][MAXWEIGTH];
/********************************************************************************************************************************
0-1背包问题 Version 1.0
2008-10-28
********************************************************************************************************************************/
//计算背包能装进物品的最大价值
void knapsack(int v[],int w[],int t,int len)
{
	int n = len;
	int jMin = (w[n]-1>=t)?t:w[n]-1;//= min(w[n]-1,t);


	for (int j=0;j<=jMin;j++)
	{
		c[n][j] = 0;
	}
	for (int jLarger=w[n]; jLarger<=t; jLarger++ )
	{
		c[n][jLarger] = v[n];
	}

	
    for (int i=n-1; i>1;i--)
    {
	
		jMin = (w[i]-1>=t)?t:w[i]-1;
		for (int k1=0 ; k1<=jMin;k1++)
		{
			c[i][k1] = c[i+1][k1];
		}
		for (int k2=w[i]; k2<=t;k2++)
		{
			c[i][k2] = (c[i+1][k2]>= c[i+1][k2-w[i]]+v[i])?c[i+1][k2]:c[i+1][k2-w[i]]+v[i];
		}
    }

	c[1][t] = c[2][t];
	if (t>=w[1])
	{
		c[1][t] = (c[1][t]>=c[2][t-w[1]]+v[1])?c[2][t]:c[2][t-w[1]]+v[1];
	}
	cout<<"背包能容纳物品的最大价值是: ";
    cout<<c[1][t]<<endl;
}

//查找背包是否被装入
void trace(int w[], int t,int x[],int len)
{
	cout<<"最优装载物品的结果:（0—表示不装入，1—表示装入）:"<<endl;
	for (int i=1;i<len;i++)
	{
		if (c[i][t]==c[i+1][t])
		{
			x[i] = 0;
		}
		else {
			x[i] = 1;
			t-=w[i];
		}
		cout<<x[i]<<" ";
	}
	x[len]=(c[len][t]>0)?1:0;
	cout<<x[len]<<endl;
}

void main()
{

    int count = 0;
	int W = 0;
	cout<<"请输入背包的容量(整数且小于200):";
	cin>>W;

	cout<<"请输入物品的个数（整数且小于200）:";
	cin>>count;

	int *v =(int *)malloc((count+1)*sizeof(int));
	int *w =(int *)malloc((count+1)*sizeof(int));
	int *x =(int *)malloc((count+1)*sizeof(int));
	
	cout<<"请输入"<<count<<"个物品的重量："<<endl;
	for (int j=1;j<=count;j++)
	{
		cin>>w[j];
	}
//	cout<<endl;

    cout<<"请输入"<<count<<"个物品的价值: "<<endl;
	for (int j1=1;j1<=count;j1++)
	{
		cin>>v[j1];
	}
	cout<<endl;
	
    knapsack(v,w,W,count);
    trace(w,W,x,count);
}