题目链接：51nod1085 背包问题
问题描述：
有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过m的物品，求所有挑选方案中价值总和的最大值。
思路分析：
问题可以看做往一个载重量为m的背包中装入有限数量的物品，求装入物品的最大价值。这里物品的件数都为1，所以每个物品都只有两种选择，要么放入背包，要么不放。在背包容量为j时，对前i件物品来说，设它的最大价值为dp[i][j]，它的最大价值状态转移公式为：
//当第i件物品比背包容量还大时，dp[i][j]等于前i-1件物品放入这个背包的最大价值。
dp[i][j]=dp[i-1] [j] (j<w[i])
//当第i件物品能放入背包时，分为两种情况，选择放和不放，不放的话和上面公式相同，放的话则背包容量减去第i件物品的重量再去装前i-1件物品，所得的最大价值加上第i件物品的价值。两种情况中较大的那种即为最优解。
dp[i][j]=max(dp[i-1] [j],dp[i-1] [j-w [i] ]+v[i]) (j>=w[i])
参考代码：
#include"cstdio"
#include"algorithm"
using namespace std;
int N,W;
int w[105],p[105];
int dp[10007][105]= {0};
void DP()
{
for(int i=1; i<=W; i++)
for(int j=1; j<=N; j++)
dp[i][j]=w[j]<=i?max(dp[i-w[j]][j-1]+p[j],dp[i][j-1]):dp[i][j-1];
}
int main()
{
scanf("%d%d",&N,&W);
for(int i=1; i<=N; i++)
scanf("%d%d",&w[i],&p[i]);
DP();
printf("%d\n",dp[W][N]);
return 0;
}
看了dd大牛的背包九讲后，对于01背包问题又有了更深层次的理解，从上面的分析可以看出，在每次更新dp数组时，总是在当前物品数-1的基础上的，能不能直接用一维数组来保存物品数-1时的值呢？只需把空间花费从大到小来构成for循环即可。
参考代码：
#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
int N,W;
int w[105],p[105];
int dp[10005];
void DP()
{
for(int i=1;i<=N;i++)
for(int j=W;j>0;j--)
{
dp[j]=w[i]<=j?max(dp[j-w[i]]+p[i],dp[j]):dp[j];
}
}
int main()
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&N,&W);
for(int i=1;i<=N;i++)
{
scanf("%d%d",&w[i],&p[i]);
}
DP();
printf("%d\n",dp[W]);
return 0;
}