问题描述
有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：物品数量＝4，背包容量(V)＝8 ，物品的体积(W)和价值(V)如下：
背包问题的解决过程：
首先定义为一些变量，方便描述方便：
Xi：第i个物品的选择（xi = 1 代表选择该物品，0则代表不选）
Vi：代表第i个物品的价值，
Wi：代表第i个物品的体积
- 建立模型：问题的解为求 Max(X1V1 + X2V2 + ......+XnVn)
- 约束条件：X1W1 + X2W2 + ......+XnWn <= V
-
确定递推关系式：
定义f(i,j)，表示前 i 个物品装入容量为 j 的背包的最大价值。
此时对于第 i 个物品，有两种可能：
- 背包剩余容量不足以容纳该物品，此时背包的价值与前i-1个物品的价值是一样的，f(i,j) = f(i-1,j)
- 背包剩余容量可以装下该商品，此时需要进行判断，因为装了该商品不一定能使最终组合达到最大价值，如果不装该商品，则价值为：f(i-1,j)，如果装了该商品，则价值为f(i-1,j-wi) + vi，从两者中选择较大的那个。
所以就得出了递推关系式：
j < Wi: f(i,j) = f(i-1,j)
j >= Wi: f(i,j) = Max( f(i-1,j)，f(i-1,j-wi) + vi )
-
确定初始值：
01背包问题一般有两种不同的问法：
（1）一种是恰好装满背包的最优解，要求背包必须装满，那么在初始化的时候，除了f(0)(0)为0，其他的f(j)(1 <= j <= 背包容量)都应该设置为−∞，这样就可以保证最终得到的f(i)(j)是恰好装满背包的最优解。
（2）另一种问法不要求装满，而是只希望最终得到的价值尽可能大，那么初始化的时候，应该将f(j)(0 <= j <= 背包容量)全部设置为0。
为什么呢？
因为初始化的数组，实际上是在没有任何物品可以放入背包的情况下的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么都不装且价值为0的情况下被“恰好装满”，其他容量的背包均没有合法的解，因此属于未定义的状态，应该设置为−∞。如果背包不需要被装满，那么任何容量的背包都有合法解，那就是“什么都不装”。这个解的价值为0，所以初始状态的值都是0。
递归解法：
class Solution {
// 体积
let volumn:[Int] = [0,2,3,4,5]
// 价格
let price:[Int] = [0,3,4,5,6]
func findMaxPrice(_ capital: Int) -> Int {
let maxPrice = dfs(volumn.count - 1, left: capital)
return maxPrice
}
func dfs(_ i: Int,left capital: Int) -> Int {
var result = 0
if capital == 0 || i == 0 {
result = 0
} else if capital < volumn[i] {
result = dfs(i - 1, left: capital)
} else {
let tmp1 = dfs(i - 1, left: capital)
let tmp2 = dfs(i - 1, left: capital - volumn[i]) + price[i]
result = max(tmp1, tmp2)
}
return result
}
}
每个物品需要递归调用两次，时间复杂度：O(2n)，n为物品数量
动态规划解法：
判断是否可以使用动态规划求解：
最优化原理:使用反证法：
假设(x1，x2，…，xn)是01背包问题的最优解，则有(x2，x3，…，xn)是其子问题的最优解，假设(y2，y3，…，yn)是上述问题的子问题最优解，则有(v2y2+v3y3+…+vnyn)+v1x1 > (v2x2+v3x3+…+vnxn)+v1x1。说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理。
无后效: 对于任意一个阶段，只要背包剩余容量和可选物品是一样的，那么我们能做出的现阶段的最优选择必定是一样的，是不受之前选择了什么物品所影响的。即满足无后效性。
class Solution {
// 体积
let volumn:[Int] = [0,2,3,4,5]
// 价格
let price:[Int] = [0,3,4,5,6]
func findMaxPrice(_ capital: Int) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: capital + 1), count: volumn.count)
for i in 1..<volumn.count {
for j in 1...capital {
if j < volumn[i] {
dp[i][j] = dp[i - 1][j]
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volumn[i]] + price[i])
}
}
}
return dp[volumn.count - 1][capital]
}
}
两次循环遍历嵌套，时间复杂度O(n*c)，n为物品的数量，c为背包容量
比较递归和动态规划解法时间复杂度：O(2n) 、 O(n*c)，可以预见，当数据量越大，相比递归算法，动态规划用于有力的优势
01背包算法优化：
上方法的时间和空间复杂度均为O(NC)，时间复杂度已经不能再优化了，但空间复杂度却可以优化到O(C).
回头看下之前的递推关系式：
j < Wi: f(i,j) = f(i-1,j)
j >= Wi: f(i,j) = Max( f(i-1,j)，f(i-1,j-wi) + vi )
可以发现，每次求解 f(i,j)只与f(i-1,m) {m:1...j}有关。也就是说，如果我们知道f(i-1,1...j)就肯定能求出f(i,j)，为了更直观的理解，请看下面表格：
class Solution {
// 体积
let volumn:[Int] = [0,2,3,4,5]
// 价格
let price:[Int] = [0,3,4,5,6]
func findMaxPrice(_ capital: Int) -> Int {
var dp = Array(repeating: 0, count: capital + 1)
for i in 1..<volumn.count {
//注意：j需要按照 背包最大容量...0的逆序来循环
for j in (volumn[i]...capital).reversed() {
dp[j] = max(dp[j], dp[j - volumn[i]] + price[i])
}
}
return dp[capital]
}
}
注意：使用一维数组时，j 应按照
背包容量 -> w[i]的顺序进行遍历，即逆序遍历。这是为了保证第 i 次循环中的状态f[i][j]是由组状态f[i−1][j−w[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果f[i−1][j−w[i]]。
那为什么会这这样呢？
相比二维数组的背包把各个状态都保存了下来，一维数组的背包是会覆盖之前的状态的，即 f[j] 的第 i 次遍历结果会覆盖第 i - 1 的结果：
f[j]表示在执行i次循环后(此时已经处理iii个物品)，前 i 个物体放到容量 j 的背包时的最大价值，即之前的 f[i][j]。与二维相比较，它把第一维压去了，但是二者表达的含义是相同的，只不过 f[j] 一直在重复使用，所以，也会出现第i次循环覆盖第i−1次循环的结果。
这个说可能有点抽象，用表格解释下
-
j正序枚举：0 -> 背包容量
等我们在填充到6这个位置时，发现还可以造成更大的价值，也就是把这个物品再用一遍
-
j逆序枚举：背包容量 -> 0
此时，在体积为6的背包中有了价值为4的物品，但体积为3的背包中物品的价值仍然为0，也就是说填充体积为6的背包只得到了填充体积为3的背包的价值，等再枚举到体积为3的背包时，我们才填充了体积为3的背包，接下来枚举物品是就不会再重复使用这个物品了，所以这个物品只被放了一次，最后的状态是这样的
也就是为什么01背包要倒序枚举的原因。
还没看明白的话，还有一篇更详细的——点这里
网友评论