写在前面的话： 人被打击得多了，好像对什么都开始麻木了
本文主要是关于完全背包和01背包的对比
完全背包练习题：这里
01背包练习题：这里
我们来考虑一个问题背景，现在你在荒野求生，帐篷已经搭好了，在夜晚正要准备睡觉的时候，突然你发现有狼群再以一定的速度包围你，于是你要收拾东西赶快跑，但是这个时候你发现你的背包所剩无几，能拿的东西也拿不了多少了。这个时候你对每一件物品进行价值估计，比如说，笔记本电脑是最贵的，价值在6000~8000，但是重量较轻。饮用桶装水价值在1000左右（荒野没有水），但是重量十分大。诸如此类，你拿起背包开始装。你需要在一定的背包重量下选择哪一件物品来装。这就是01背包，涉及到取舍的问题，每一件物品只有一件，对于你来说只有装和不装。
而涉及到的状态转移方程为：

for(int i=0;i
for(int j=max_weight-weight[i];j>=0;j--)
{
dp[j+weight[i]]=max(dp[j+weight[i]],dp[j]+price[i]);
}
}

这里的dp[i]就是在装i重量时，所获得的最大价值。
如果用二维dp来表示，则可以写成：

for(int i=0;i
for(int j=weight[i];j<=max_weight;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i]);
}}

注意这里会发现j的行进方向和一维的略有不同，一维的行进方向不能改变，但是二维的可以。证明省略。
如果是完全背包的话，就是这样的问题背景。假设你去自助餐厅吃饭，交了钱之后就可以随便吃，并且假设每一种食物供应充足。这个时候你会发现你的胃容量是有限的，如果吃了价值很高但是十分大的食物，比如龙虾，你的胃就不剩多少地方了。如果你只吃便宜的但是也很占胃的东西，比如米饭，你就会更亏。于是，你搜集来了餐厅中所有食物的价格和卡路里表，你要计算出，在有限胃容量下，能吃到的食物的最大价值。（假设老板给你的时间足够，一般是3个小时）
这时的动态转移方程可以写作如下的形式：

dp[0]=1;
for(int i=0;i
for(int j=0;j
dp[j+weight[i]]=max(dp[j+weight[i]],dp[j]+price[i]);
}}

在这里我们会发现，这个和一维的01背包相差不大
我们做一下对比。

不知你是否注意，仅仅是行进方向的不同？
我们记从1->n的行进方向为向右行进。也就是1为左，n为右。这里我们会发现，向左行进但是用左的数更新右的数值时，右的数值不会对下一次更新产生任何影响。但是如果行进方向改变，右的数值就会对左的数值产生改变。
而01背包不允许一个物品放两次，所以行进是放进去一个之后就不允许该物品再次进入背包，但是完全背包无所谓。
完全背包的二维dp可以写成这样，可能会增强你的理解。

for(int i=0;i
for(int j=0;j<=max_weight;j++)
{
for(int k=0;j+k*weight[i]<=max_weight;j++)
{
dp[i][j+k*weight[i]]=max(dp[i][j+k*weight[i]],dp[i][j]+k*price[i]);
}}}

dp[i][j]的含义为装入前i个物品耗费j重量时的最大值。