一维01背包 POJ3624

集训期间学会了动态规划的01背包，想去刷几道水题看看代码有没有问题，没想到遇到POJ3624，我原来的二维背包因为数据太大而不能AC，然后我到网上查看一下别人的方法，才看见，背包问题可以用一维！仔细想一下，对啊，这道题，用一维数组更新其值就可以了。于是重写代码，AC。代码如下：

#include <stdio.h>
#include <string.h>
#define N 3500
#define M 13000
int d[N],w[N],val[M],n,W;

void knapsack()
{
	int i,j;
	memset(val,0,sizeof(val));
	for(i=1;i<=n;i++)
		for(j=W;j>=1;j--)
		{//当前背包容量比第i件物品体积大，且当前价值比更新后价值小，则更新
			if(j>=w[i]&&val[j-w[i]]+d[i]>val[j])
				val[j]=val[j-w[i]]+d[i];
		}
	return ;
}

int main()
{
	int i;
	while(scanf("%d%d",&n,&W)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d%d",&w[i],&d[i]);
		knapsack();
		printf("%d\n",val[W]);
	}
	return 0;
}