0-1beibao.cpp

0-1背包问题的动态规划求解算法, 0-1背包不同于背包问题

#include"stdio.h"

#define C 6	//背包容量
#define N 4		//物品数量
int V[N+1]={0,7,10,3,5};		//N个物品的价值
int W[N+1]={0,2,4,8,3};	//N个物品的重量

//#define C 10	//背包容量
//#define N 5		//物品数量
//int V[N+1]={0,6,3,5,4,6};	//N个物品的价值(0号不用)
//int W[N+1]={0,2,2,6,5,11};		//N个物品的重量(0号不用)

int M[N+1][C+1]={0};	//x坐标为背包容量的递增，y轴由底向上产生结果，每层代表选出一个物品，有N-1层
int X[N+2];		//构造最优值用(可装N个物品)

//v:各个物品的价值
//w:各个物品的重量
//c:背包容量
//n:最后一个物品在v和w中对应的下标
//m:保存结果的数组，x坐标为背包容量的递增，y轴由底向上产生结果，每层代表选出一个物品，有N-1层
void knapsack(int v[],int w[],int c,int n,int m[][C+1])
{
	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>=0;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 m[][C+1], int w[],int c,int n, int x[])
{
	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;
}

void main()
{
	int i,j;
	
	printf("物品数目：%d",N);
	printf("\n物品重量：");
	for(i=1; i<=N; i++) printf("%2d ",W[i]);
	printf("\n物品价值：");
	for(i=1; i<=N; i++) printf("%2d ",V[i]);
	printf("\n背包容量：%d\n\n",C);

	knapsack(V,W,C,N,M);

	for(i=0;i<=N;i++)	X[i]=-1;
	Traceback(M,W,C,N,X);

	printf("   ");
	for(i=1; i<=C; i++) printf("%4d]",i);
	printf("\n");
	for(i=1;i<=N;i++)
	{
		printf("(%d)",i);
		for(j=1;j<=C;j++)
			printf("%5d",M[i][j]);
		printf("\n");
	}

	printf("取出的物品编号: ");
	for(i=1;i<=N;i++)	
		if(X[i]==1) printf("%3d",i);
	printf("\n");
}