bagage.cpp

算法设计中的0-1背包问题

//用动态规划法求解0-1背包问题, n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}.

#include<stdio.h>
#include<stdlib.h>

void record(int n, int c, int *w, int *v, int **m, int **x);
void find(int **x, int n, int *w, int *v, int c);
int min(int a, int b);

void main()
{
	int i=0, n, c, *w, *v, **m, **x;

	printf("n = ");
	scanf("%d",&n);

	printf("c = ");
	scanf("%d",&c);

	w = (int*)malloc((n+1)*sizeof(int));
	v = (int*)malloc((n+1)*sizeof(int));
	m = (int **)malloc((n+1)*sizeof(int *));
	x = (int **)malloc((n+1)*sizeof(int *));
	if(w==NULL||v==NULL||m==NULL||x==NULL)
	{
		printf("No Enough Memory!");
		exit(0);
	}

	for(i=1; i<=n; i++)
	{
		m[i] = (int *)malloc((c+1)*sizeof(int));
		x[i] = (int *)malloc((c+1)*sizeof(int));
		if(m[i]==NULL||x[i]==NULL)
		{
			printf("No Enough Memory!");
			exit(0);		
		}
	}

	i = 0;
	while(++i<=n)
	{
		printf("w[%d] = ",i);
		scanf("%d",w+i);
		printf("v[%d] = ",i);
		scanf("%d",v+i);
	}

	record(n, c, w, v, m, x);
	find(x, n, w, v, c);

	printf("\nW = %d\n",m[1][c]);

	free(w);
	free(v);
	for(i=1; i<=n; i++)
	{
		free(m[i]);
		free(x[i]);
	}
	free(m);
	free(x);
}


//一定要注意，m[i][j]的含义是剩余物品是第i个物品之后的（包括第i个）时，若包中还剩载重为j，
//此时最多还可以装多少。故m[n][j]的值可以通过比较w[n],c,j直接得出，从而确定了第n行，
//然后逆过来确定其它行即可，这里也是典型的用矩阵建立备忘录。
void record(int n, int c, int *w, int *v, int **m, int **x)
{
	int i = 0, j = 0;
	
	int Maxj = min(c, w[n]-1);
	for(j = 1; j <= Maxj; j++)
	{
		m[n][j] = 0;
		x[n][j] = 0;
	}
	for(j = Maxj+1; j <= c; j++)
	{
		m[n][j] = v[n];
		x[n][j] = 1;
	}//用了点小技巧。

	
	
	for(i = n-1; i > 1; i--)//第1行只需要知道m[1][c]，故不用在此循环。
	{
		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];
				x[i][j] = 0;
			}
			else
			{
				m[i][j] = m[i+1][j-w[i]]+v[i];
				x[i][j] = 1;
			}
		}
		for(j=1; j<w[i]; j++)
		{
			m[i][j] = m[i+1][j];
			x[i][j] = 0;
		}

	}
	
	
	if(c > w[1])
	{
		if(m[2][c] >= m[2][c-w[1]]+v[1])
			//加了=就使所得解在价值最大时，物品数最少；反之物品数最多。
		{
			m[1][c] = m[2][c];
			x[1][c] = 0;
		}
		else
		{
			m[1][c] = m[2][c-w[1]]+v[1];
			x[1][c] = 1;
		}
	}
	else
	{
		m[1][c] = m[2][c];
		x[1][c] = 0;
	}

}

void find(int **x, int n, int *w, int *v, int c)
{
	int i = 0, j = c;

	while(++i <= n)
		if(x[i][j])
		{
			printf("\nNO.%d: w = %d, v = %d ", i, w[i], v[i]);
			j -= w[i]; 
		}
}


int min(int a, int b)
{
	if (a >= b)	return b;
	else return a;
}