题目链接
http://poj.org/problem?id=3624
题意
给定N种物品的价值v[i]和重量w[i]，每一种物品只有一个，求用一个最多能装重量为M的背包所能装物品的最大价值。
题解
01背包问题。
设dp[i]表示容量为i的背包所能获得的最大价值。
决策：第i种物品是否放入背包。
状态转移方程：dp[i]=max(dp[i],dp[i-w[i]]+v[i])。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxv=2e4+100;
const int maxn=4e3+100;
int N,V,dp[maxv],w[maxn],v[maxn];int main()
{while(~scanf("%d%d",&N,&V)){memset(dp,0,sizeof(dp));for(int i=1;i<=N;i++)scanf("%d%d",&w[i],&v[i]);for(int i=1;i<=N;i++)for(int j=V;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);printf("%d\n",dp[V]);}return 0;
}