01背包问题 #
有N 件物品和一个容量为bag 的背包。第i 件物品的重量是w[i]，价值是v[i]。 求解将哪些物品装入背包可使价值总和最大。
暴力算法 #
我们首先想到的应该是穷举所有的可能，然后把最好的那一个给返回。而在穷举的过程种我们需要考虑的问题仅仅是对于第i个物品，到底要不要把它放入背包。所以可以用递归的方式很自然地解决。
/**
*
* @param w 物品的重量
* @param v 物品的价值
* @param i 第i个物品
* @param alreadyW 已经放入背包的重量
* @param bag 背包所能承受的最大重量
* @return 最大价值
*/
public static int recur(int[] w,int[] v,int i,int alreadyW,int bag){
if(alreadyW > bag || i >= w.length) return 0; //背包超重或者没有物品可以装
int totalVal1 = 0,totalVal2 = 0;
totalVal1 = recur(w,v,i+1,alreadyW,bag); //第i个物品不放入背包
if(alreadyW+ w[i] <= bag)
totalVal2 = recur(w,v,i+1,alreadyW+ w[i],bag) + v[i]; //第i个物品放入背包
return Math.max(totalVal1,totalVal2);
}
或者用背包的剩余容量来表达
public static int recur(int[] w,int[] v,int i,int bag){
if(bag < 0 || i >= w.length) return 0; //背包超重或者没有物品可以装
int totalVal1 = 0,totalVal2 = 0;
totalVal1 = recur(w,v,i+1,bag); //第i个物品不放入背包，这里的bag指的是剩余的容量
if(bag >= w[i])
totalVal2 = recur(w,v,i+1,bag - w[i]) + v[i]; //第i个物品放入背包
return Math.max(totalVal1,totalVal2);
}
动态规划1.0 #
如果用递归的方式会造成很多重复的计算，所以可以考虑动态规划的方法来计算,我们可以用数组缓存一些中间的结果，避免重复计算。
public static int bag(int[] w, int[] v, int bag) {
// 用一个数组来缓存中间步骤的结果
int[][] dp = new int[w.length][bag + 1];
// 初始化第0行，第0列已经被初始化为0
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = i - w[0] >= 0 ? v[0] : 0;
}
// 前i件物品当背包的容量为j时的最优解
for (int i = 1; i < w.length; i++) {
for (int j = 1; j <= bag; j++) {
if (j - w[i] < 0) { // 背包的容量装不下第i件物品
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
}
return dp[w.length - 1][bag];
}
动态规划2.0 - 优化空间复杂度 #
目前看起来时间复杂度上面似乎没有更好的优化方案，我们可以考虑从空间复杂度上面入手。从上面的状态转移方程我们可以看出，对于低K个物品的最优解，似乎我们只需要知道第K-1个物品的最优解就可以。那我们是不是可以尝试只保留前一个物品的最优解呢，答案当然是肯定的。
只要我们接受dp中保存着K-1个物品的最优解，就可以把dp数组变成一维，如下面的代码所示。不过这是需要注意的一点就是第二层循环只能从背包的容量bag开始，到0结束。因为后面的值需要前面的值才能导出，
比如K-1时dp数组的值为 1，2，3，3，4
此时我们更新dp数组的顺序应该是 1，2，3，3，5
1，2，3，4，5
从后往前更新，如果从前往后更新的话可能会把dp数组刷新，这时得到的结果就会出错。
public static int fixBag(int[] w, int[] v, int bag) {
// 用一个数组来缓存中间步骤的结果
int[] dp = new int[bag + 1];
//初始化数组
for (int i = 0; i < dp.length; i++) {
dp[i] = i - w[0] >= 0 ? w[0] : 0;
}
// 前i件物品当背包的容量为j时的最优解
for (int i = 1; i < w.length; i++) {
for (int j = bag; j >= 0 ; j--) {
if(j - w[i] >= 0)
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[bag];
}
完全背包问题 #
有N 种物品和一个容量为bag 的背包。第i 种物品的重量是w[i]，价值是v[i]。每种物品可以被放入多个且没有上限。 求解将哪些物品装入背包可使价值总和最大。
动态规划1.0 #
这种情况下一种很直观的想法就是把没有限制的物品变成有限制的物品，让这道题的类型和01背包一致。我们可以假设如果背包里只放一种物品，那么对于N种物品来说就分别需要放入$K_i$个 (0< I < N)，那也就是说总共也就相当于只有$\sum{K_i}$个物品，只不过这些物品里有些物品的重量和价值是一样的，这样的话我们就能用01背包的方式来做这道题了，一种相对优雅的解法如下： $$ f[i][j] =max{f[i-1][j - k * w[i]]+ k * v[i]} $$
public static int completeBag(int[] w, int[] v, int bag) {
// 用一个数组来缓存中间步骤的结果
int[][] dp = new int[w.length][bag + 1];
// 初始化第0行，第0列已经被初始化为0
// 只能放第0件物品，在最大承重为i时的最大价值
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = (i / w[0]) * v[0];
}
// 前i件物品当背包的容量为j时的最优解
for (int i = 1; i < w.length; i++) {
for (int j = 1; j <= bag; j++) {
int nCount = j / w[i];
for (int k = 0; k < nCount; k++) {
dp[i][j] = Math.max(dp[i - 1][j], (dp[i - 1][j - k * w[i]] + k * v[i]));
}
}
}
return dp[w.length - 1][bag];
}
我们也很容易发现这种情况下计算的复杂度也很高，我们甚至多加了一次需要遍历$K_i$次的循环，那么有没有什么办法可以继续优化一下呢？答案当前也是有的。
动态规划2.0 #
我们先来看这段优化后的代码
public static int fixCompleteBag(int[] w, int[] v, int bag) {
// 用一个数组来缓存中间步骤的结果
int[][] dp = new int[w.length][bag + 1];
// 初始化第0行，第0列已经被初始化为0
// 只能放第0件物品，在最大承重为i时的最大价值
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = (i / w[0]) * v[0];
}
// 前i件物品当背包的容量为j时的最优解
for (int i = 1; i < w.length; i++) {
for (int j = 0; j <= bag ; j++ ) {
if(j - w[i] < 0)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
}
}
return dp[w.length - 1][bag];
}
这段代码的循环体部门看起来是不是有种似曾相识的感觉。没错，它就是01背包动态规划2.0的解法，将容量从bag到0给倒过来了。在01背包中我们要确保用到的是K-1种物品的最优值，所以是从后往前循环。但是在没有数量限制的情况下，我们不需要考虑我们用到的是第K种的缓存还是第K-1种的缓存，我们只在乎它最优的那种形式。
多重背包问题 #
有N 种物品和一个容量为bag 的背包。第i 种物品的重量是w[i]，价值是v[i]。每种物品有n[i]个。 求解将哪些物品装入背包可使价值总和最大。
这种情况的限制更加具体，但是我们同样可以考虑用01背包的那种方式。还记得我们是怎么样把完全背包变成01背包的形式的吗。没错，我们可以假设背包内放同一种物品能放多少来界定这种物品的最大数量。现在题目中已经帮我们定好了数量是多少，我们只需要带入进去用同样的方式就能得到答案。 $$ dp[i][j] = max(dp[i-1][j],dp[i-1][v-kw[i]]+kv[i]) $$
$$
public static int multiBag(int[] w, int[] v,int[] n,int bag) {
// 用一个数组来缓存中间步骤的结果
int[][] dp = new int[w.length][bag + 1];
// 初始化第0行，第0列已经被初始化为0
// 只能放第0件物品，在最大承重为i时的最大价值
for (int i = 0; i < dp[0].length; i++) {
int k = i /w[0];
if( k <= n[0]) {
dp[0][i] = k * v[0];
}else {
dp[0][i] = n[0] * v[0];
}
}
// 前i件物品当背包的容量为j时的最优解
for (int i = 1; i < w.length; i++) {
for (int j = 1; j <= bag; j++) {
for (int k = 0; k < n[i]; k++) {
dp[i][j] = Math.max(dp[i - 1][j], (dp[i - 1][j - k * w[i]] + k * v[i]));
}
}
}
return dp[w.length - 1][bag];
}
Last modified on 2022-02-24