01背包问题的理解,java代码实现,算法初学者必看
01背包问题
1.1 题目
有n件物品和一个容量为v的背包，放入第i件物品耗费的空间是Ci，得到的价值是Wi。
求解将哪些物品装入背包可以使价值总和最大
1.2 思路
用子问题定义状态：即F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
即将前i件物品放入容量为v的背包中这个子问题，若只考虑第i件物品的策略（放或不放），
那么就可以转化为一个只和前i − 1件物品相关的问题。
如果不放第i件物品，那么问题就转化为“前 i−1件物品放入容量为v的背包中”，价值为F[i−1, v]；
如果放第i件物品，那么问题就转化为“前 i−1件物品放入剩下的容量为v − Ci的背包中", 此时能获得的最大价值就是F[i − 1, v − Ci]再加上通过放入第i件物品获得的价值Wi。
public static int[][] fun(int v, int n, int[] c, int[] w){
int[][] f = new int[n+1][v+1];
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[0].length; j++){
f[i][j] = 0;
}
}
for (int i = 1; i < f.length; i++) {
for (int j = 1; j < f[0].length; j++){
if(j>=c[i-1]){
f[i][j] = Math.max(f[i-1][j],f[i-1][j-c[i-1]] + w[i-1]);
}
else {
f[i][j] = f[i-1][j];
}
}
}
return f;//f是一个二维数组，用于存储f[i][j]其中i为前i件物品，j为当前背包容量，f为获得价值
1.3 优化
显然，上述代码是可以优化的。可以优化其空间复杂度。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i = 1..N，每次算出来二维数组F[i, 0..V ]的所有值。那么，如果只用一个数组F[0..V]，能不能保证第i次循环结束后F[v]中表示的就是我们定义的状态F[i, v]呢？F[i, v]是 由F[i-1, v]和F[i-1, v-Ci]两个子问题递推而来，能否保证在计算F[i,v]时（也即在第i次主循环中计算F[v]时）
能够取用F[i-1, v]和F[i-1, v-Ci]的值呢？
事实上，这要求在每次主循环中我们以v = V..0的递减顺序计算F[v]，这样才能保证计算F[v]时F[v-Ci]保存的是状态F[i-1, v-Ci]
的值.
public static int[] betterFun(int v, int n, int[] c, int[] w){
int[] f = new int[v+1];
for (int i = 1; i < n + 1; i++) {
for (int j = f.length - 1; j > 0; j--){
if(j>=c[i-1]){
f[j] = Math.max(f[j],f[j-c[i-1]] + w[i-1]);
}
else {
f[j] = f[j];
}
}
}
return f;
}
为什么要递减计算呢? 因为在第i次循环的j循环中,需要上一次i循环即i-1循环保存的f值,即需要f[j-c[i-1]]的值(c[i-1]一定是大于等于零的,所以要计算当前f[j]的值,需要比它小的i-1层保存的f[j-c[i-1]]).这时,j从0...v的递增循环过程会覆盖掉原先的值,而如果是递减则不会覆盖.
1.4 f的初始化
刚才问题的需求为找到在空间满足的情况下找到最优解,但如果题目还有一个要求是必须装满背包,那应该怎么处理?
很简单,在初始化f[0...v]时,将f[0]设为0,将f[1...v]设为-∞,最终得到的f[v]一定是一种恰好装满背包的最优解.
why? 可以从i为1时分析,j从大往小遍历,如果f[j-c[i-1]]为负无穷,则保持不变仍为负无穷,直到j-c[i-1]为0时,才会将当前i放入背包,再进行下一次迭代.这样,如果f[v]不能刚好把背包填满,f[v]就一直是负无穷大.所以,可以得到满背包的最优解.
而初始化的数组可以这样理解:初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
1.5 一个常数的优化
代码中的for (int j = f.length - 1; j > 0; j--)可以被优化
首先明显可以看出来如果j<c[i-1]的话是不需要转换的,所以上述代码可以简化为
public static int[] bestFun(int v, int n, int[] c, int[] w){
int[] f = new int[v+1];
for (int i = 1; i < n + 1; i++) {
for (int j = f.length - 1; j >= c[i-1]; j--){
f[j] = Math.max(f[j],f[j-c[i-1]] + w[i-1]);
}
}
return f;
}
之后,仍可优化
即当v很大时，可以将从第i个到后面所有的物品全部装入背包且剩余空间还大于第i个物品的空间，那么可以减少不必要的循环, 这里就不给出代码了
1.6 小结
动态规划是各类面试笔试机试非常喜欢提问的问题, 学好了动态规划,算法中的很多问题都可以解决,同时还需要理解其空间优化的思想和状态转移方程的构建方法. 本篇为背包9讲的第一讲,个人学习,欢迎指正.