背包问题 动态规划法.txt

ACM资料大集合

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

//背包问题

/*
测试数据：
输入：
8 23
8 4 5 1 6 6 7 3
7 8 3 3 4 9 6 2
输出：
1 0 1 0 1 0 1 1
*/
int num,c;
int v[10];
int w[10];
int m[10][30];//设m[i][j],则表示在前i个物品中，背包大小是j的情况下，背包所装东西的最大价值

void knapsack()
{
	int n=num-1;
	int jmax,i,j;
	if(w[n]<c) jmax=w[n];
	else jmax=c;
	for(i=0;i<jmax;i++)
		m[n][i]=0;
	for(i=w[n];i<=c;i++)
		m[n][i]=v[n];
	for(i=n-1;i>0;i--)
	{
		if(w[i]<c) jmax=w[i];
		else jmax=c;
		for(j=0;j<jmax;j++)
			m[i][j]=m[i+1][j];
		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-w[i]]+v[i];
			else
				m[i][j]=m[i+1][j];
		}
	}
	m[0][c]=m[1][c];
	if(c>=w[0])
	{
		if(m[0][c]<m[1][c-w[0]]+v[0])
			m[0][c]=m[1][c-w[0]]+v[0];
	}
}

void trackback(int *x)
{
	int n=num-1;
	int i;
	for(i=0;i<n;i++)
	{
		if(m[i][c]==m[i+1][c]) x[i]=0;
		else
		{
			x[i]=1;
			c=c-w[i];
		}
	}
	if(m[n][c]>0) x[n]=1;
	else x[n]=0;
}
int main()
{
	int i,x[10],j;
	scanf("%d %d",&num,&c);
	for(i=0;i<num;i++)
		scanf("%d",&v[i]);
	for(i=0;i<num;i++)
		scanf("%d",&w[i]);
	knapsack();
	for(i=0;i<=c;i++) printf("%3d",i);
	printf("\n");
	for(i=0;i<num;i++)
	{
		for(j=0;j<=c;j++)
			printf("%3d",m[i][j]);
		printf("\n");
	}
	trackback(x);
	for(i=0;i<num;i++)
		printf("%d ",x[i]);
	printf("\n");
	return 0;
}