传送门：http://poj.org/problem?id=3624

题目大意：XXX去珠宝店，她需要N件首饰，能带的首饰总重量不超过M，要求不超过M的情况下，使首饰的魔力值（D）最大。

0-1背包入门题。

可构建状态转移方程：

dp [ i ] [ v ]= max ( dp[ i-1 ] [ v ], dp[ i-1 ][ v- W[ i ] ]+d[ i ] ] )

但是这样空间太大，可以用滚动数组解决。

		for(int i=1;i<=N;i++)

		{

			for(int j=M;j>=w[i];j--)

			{

				f[j]=max ( f[j] , f[j-w[i]]+d[i]);

			}

		}

为什么这样做是正确的呢？f数组是从上到下，右到左计算的，计算f ( i, j)之前， f( j )保存的就是 f(i-1 ,j)的值，f ( j-w ）就是 f(i-1 ,j-w)的值，所以f[j]=max ( f[j] , f[j-w[i]]+d[i]); 就把

f(i-1 ,j-w[i]) +d[i] 和 f(i-1 ,j)中大的保存起来。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=12880+10;

int f[MAXN],w[MAXN],d[MAXN];

int main()

{

	int N,M;

	while(~scanf("%d%d",&N,&M))

	{

		for(int i=1;i<=N;i++)

			scanf("%d%d",&w[i],&d[i]);

		memset(f,0,sizeof(f));

		for(int i=1;i<=N;i++)

		{

			for(int j=M;j>=w[i];j--)

			{

				f[j]=max ( f[j] , f[j-w[i]]+d[i]);

			}

		}

		printf("%d\n",f[M]);

	}

}

当然也可以边输入边处理：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=12880+10;

int f[MAXN],w,d;

int main()

{

	int N,M;

	while(~scanf("%d%d",&N,&M))

	{

		memset(f,0,sizeof(f));

		for(int i=1;i<=N;i++)

		{

			scanf("%d%d",&w,&d);

			for(int j=M;j>=w;j--)

			{

				f[j]=max ( f[j] , f[j-w]+d );

			}

		}

		printf("%d\n",f[M]);

	}

}