DP，Dynamic Programming.
背包问题是这样一类问题——背包有重量限制，要往背包里放物品。每样物品都有自己的价值v与重量w。问怎样放使得背包里物品的总价值最大。
参考文档：大牛之作-《背包问题九讲》
- 01背包：每样东西只有一个，要么放，要么不放，所以得名01背包
- 完全背包：每样物品都没有个数限制
- 不完全背包：不同物品的个数不尽相同

1. 01背包

1.1 背包不要求装满

1.1.1状态转移方程

dp[i][j]表示以下两种约束下的最大价值：

• 1.所装物品为前[0,i]种，不一定每种物品都要放进去；
• 2.所放物品总重量<=j。
  那么状态转移方程

1.1.2 状态初始化

dp[][]数组初始化为0.
当数组下标为负越界时也返回0.

1.2背包必须装满

1.2.1状态转移方程

同1.1.1.

1.2.2 状态初始化

1.2.3 状态初始化的比较

初始化的dp[][]数组，事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下“恰好装满”。其他容量的背包均没有合法的解，属于未定义的状态，应该被赋值为负无穷。

1.3 dp数组降维

时间与空间复杂度都为O（NW）,其中空间复杂度可以优化。
可以将dp[][]降维为一位数组dp[]。此时我们期望第i次循环后dp[j]表示的就是二维时的dp[i][j]。
那么dp[j]=f(dp[j],dp[j-w[i]]),即dp[j]的值与dp[j]和dp[j-w[i]]有关。
这要求每次主循环(i循环)中，我们要以for(int j=V;j>=0;j–){}这样的逆序来遍历。只有这样才能保证计算dp[j]时dp[j-w[i]]保存的是dp[i-1][j-w[i]]的值。反例见1.3.1.

1.3.1 关于j降序的反例

令背包总重W=2.
只有编号为0的一件物品，w[0]=1,v[0]=2。很显然，对于01背包，最大的价值V为2.
若j升序，主循环i取0时，先算dp[1]=2;再算dp[2]=max(dp[2],dp[2-w[0]]+v[0])=max(0,2+2)=4，显然不对。
降维的AC代码可参见：动态规划 HDOJ2602-Bone Collector-01背包

1.4 典型OJ题目

可参见动态规划 HDOJ2602-Bone Collector-01背包

2.不完全背包

3.完全背包

3.1状态转移方程

可以把完全背包转化为0-1背包求解。
第i件物品可以不装，可以装1件、2件、。。。、k件。根据这个思想得到状态转移方程：

3.2 合理的时间复杂度

需要减掉k这一层循环。
由于一件物品装过之后还可以再装，得到状态转移方程：

3.3典型OJ题目

可参见：动态规划 HDOJ-1114 完全背包