动态规划初步——背包问题
动态规划认知
在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
01 背包
问题
有n件物品和一个容量为m的背包，放入第ｉ件物品所需要的空间为ｗi，第ｉ件物品的价值为vｉ，问背包可以放入物品的最大价值为多少？
- 此问题不可用贪心算法，贪心法得到的往往不是最优解。
- 直接暴力穷举n件物品，时间复杂度是O(2^n)，效率过低，且存在大量重复运算。
算法
综上我们采用两重循环的方式来解决此问题，避免了复杂的递归，并且采用数组存储数据，使得计算次数大大减少，复杂度由O(2^n)优化到了O(VW)*。
for(int i=1; i<=n; i++){ //物品
for(int j=V; j>=0; j--){ //容量
if(j >= w[i]) //放得下物品，使用状态转移方程
dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
else //放不下物品，直接跳过，沿承 i-1 个物品的价值
dp[i][j] = dp[i-1][j];
}
}
优化
空间优化
实际上，二维数组的空间复杂度过高，有时候也不现实，所以有时采用状态压缩，将二维数组压缩至一维。
压缩原理：实质上，i本身无实质性意义，在第 i+1 次循环尚未开始之前，第 i 行已经保存了当前的数据，且 0 到 i-1 行就没有使用价值了，故可以将二维数组压缩为一维数组，从后向前遍历，状态转移方程中的 [i-1] 就无存在价值了。
对于外层循环中的每一个 i 值，其实都是不需要记录的，在第 i-1 次循环已结束且第 i 次循环未开始，dp数组还未更新时，dp[j]还记录着前 i-1 个物品在容量为 j 时的最大价值，这样就相当于还记录着 dp[i-1][j]和dp[i-1][j-vol[i]]+val[i]。
状态转移方程修改为 dp[j] = max(dp[j], dp[j - w[i]] + v[i])
恰好装满
如果要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。 ——《背包九讲》
可以将其理解为不能把背包填满的解都是非法（价值小于零）的，从而在计算中排除这些解。或者说当前的合法解一定是从之前的合法状态推得的。
这个技巧可以推广到其他背包问题，不仅仅限于01背包。
常数优化
经过图表可知，并不需要将表中的数据全部算出，只需要算一部分即可。因为最后所求结果为dp[n][v]，其在 n-1 行所需的最小的 j 为 v-w[n-1]，同理，对于第 i 行, j 最小循环至 v- sum{w[n...i-1]} ,综上所述我们可以优化第二层的循环次数，代码如下：
//理论上的第二层循环
// bound=max{V-sum{w[i..n]},w[i]};
// for(int j=V;j>=bound;j--)
for(i = 1; i<=n; i++){//实际代码
int sum = 0;
for(int k = i ; k <= n ; ++k){
sum += w[k];
lower = max(sum, w[i]);
for(j = V ; j >= lower; j--){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
因为若是 V-sum{w[i..n]} < w[i] 的话，则无法取到第 **i **个物品了，所以就把下限定为 w[i]，进一步减少第二层循环次数，这种方法在V很大的情况下会节省时间。
封装
//kuangbin 和 《背包九讲》 中都给出了这个代码
//此处仅仅将第二层循环和数组封装了，相当于对一个物品进行处理,但是未加入常数优化
//但是在多重背包里会用到
void ZeroOnePack(int cost,int value){
for(int j = nValue ; j >= cost ; j−−)
dp[i] = max(dp[i] , dp[i−cost] + value);
}
完全背包
问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
思考方向还是先从二维数组下手，得到转移方程，再向一维数组优化
算法
此处采用和01背包相似的思考方式，01背包每个物品都拿一次，所以对于同一个 i 下的 j 都应该是独立的，即每个 j 中至多包含一个当前物品，所以由后向前遍历，但是01背包中，每个 i 不止用一次，可能用多次，所以偏大的 j 中的情况就不应从i-1 那一行转移，而应该是从同一行中转移，这样才能保证可以出现多个 i
for(int i = 1; i <= n; i++) //正序
for(int j = 0; j <= V; j++){ //还是正序
if(j >= w[i]){ //放得下
dp[i][j] = max{dp[i-1][j] , dp[i][j-w[i]] + v[i];
} else{ //放不下
dp[i][j] = dp[i-1][j];
}
}
思维陷阱
背包问题其实有一个隐藏的条件，就是包的体积和物品的质量其实都是整数，虽说是无限多的物品，但是实质上还是枚举出来了，在 i 行的遍历一定能枚举所有含 i 情况。
完全背包每次做出选择是取决于当前这一步的，而01背包每次做出选择是取决于上一步的。主要就是因为当前这一步一个物品放过以后，表格逐渐向右填写，随着可放空间的增加，可以判断这一步是否还可以再放一个当前的物品。
优化
空间优化
和01背包一样，二维数组太过浪费空间，可以采用一维滚动数组的方式来减少空间开销。
转移方程可化为 dp[j] = max{ dp[j] , dp[j-w[i]] + v[i] }
常数优化
值得一提的是，上面的伪代码中两层 for 循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
封装
//依旧是没有常数优化
//完全背包，代价为 cost, 获得的价值为 value，也是对一个物品的处理
void CompletePack(int cost,int value){
for(int i = cost;i <= nValue;i++)
dp[i]=max(dp[i] , dp[i−cost] + value);
}
多重背包
问题
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
我们在此考虑将多重背包转化为01背包和完全背包。
- 正如在完全背包中探讨的一样，所谓“无限”只是相对无限，即背包里全部放这个东西也无法全部将其放下时，就可以认为是无限了。
- 根据此方法，剩下的所谓有限的，就可以拆分成多个物品，根据01背包来计算。但是如果拆分成 n[i] ** 个效率就太低了，所以采用二进制优化这个问题。 使这些系数分别为1 , 2, 4 , ... , 2^(k-1) , n[i]-2^k+1 ，且k是满足n[i]-2^k+1>0的最大整数。 这是因为这些数之和为n[i]** , 这样就将 n[i]个物品优化到了 log( n[i] ) 个，提高了效率。
- 此问题可以用单调队列优化至 O(VM)，即和前两种问题一样，但是太过复杂，日后补充。
void MultiplePack(int cost,int value,int amount){ //花费， 价值 ， 数量
if(cost*amount>=V) //相对“无限”
CompletePack(cost,value); //完全背包
else{
int k=1;
while(k < amount){
ZeroOnePack(k*cost,k*value); //系数递增，1，2，4，8，...
amount−=k;
k<<=1; //k左移一位，即k*=2
}
ZeroOnePack(amount*cost,amount*value);//这个不要忘记了，这是最后一个系数，即n[i]减去之前所有系数的结果
}
}
(待思考)一种实现较为简单的O(V N) 复杂度解多重背包问题的算法。基本思想是这样的：设F[i; j] 表示“用了前i 种物品填满容量为j 的背包后，最多还剩下几个第i 种物品可用”，如果F[i, j] = -1 则说明这种状态不可行，若可行应满足0 ≤ F[i,j] ≤ Mi。
优化多重背包算法
混合三种背包
问题
有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢
算法
for i=1..N
if 第i件物品属于01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品属于完全背包
CompletePack(c[i],w[i])
else if 第i件物品属于多重背包
MultiplePack(c[i],w[i],n[i])
评价
真的就这么简单粗暴，不过也体现了模块化之后的便利之处。(kuangbin模板中甚至都没有提到这个问题)
二维费用的背包问题
问题
对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为A和B。物品的价值为v[i]。
算法
费用增加一维，其实只需将状态加一维即可。设 f[i][v][u] 表示前i件物品付出两种代价分别为 v 和 u 时可获得的最大值。状态转移方程
f[i][w][u] = max{ f[i-1][w][u] ，f[i-1][w-a[i]][u-b[i]] +w[i]}
===TO BE CONTINUE==
