最常见的DP问题:背包问题

2024-04-04数据结构与算法16 分钟195 次阅读
AI 摘要salmon-ai

本文详细解析了最常见的背包类动态规划问题,从0/1背包

0/1背包

image.png

给定 n 种物品和一个背包,物品 i 的重量是 wiw_i,其价值为 viv_i,背包的容量为C。

背包问题:选择装入背包的物品,使得装入背包中物品的总价值最大

如果在选择装入背包的物品时,对每种物品 i 只有两种选择:装入背包或不装入背包,称为0/1背包问题。

与装载问题不同的是,0/1背包不能只装一部分,要么选,要么不选。

  • 可拆分的背包问题(贪心)
  • 不可拆分的背包问题(DP)

例题

有5个物品,重量分别是{2,2,6,5,4}, 价值分别为{6,3,5,4,6},背包的容量为10。求背包可以装得物品的最大价值。

分析

对于背包问题,是有模板的,我们定义一个 (n+1)x(C+1) 的二维表 dp[][],n 表示物品数量,C 表示背包容量。

dp[i][j] 表示把前 i 个物品装入背包中花费容量为 j 的获得的最大价值。i表示当前的物品下标(0 到 n),j表示当前背包的容量(0 到 C)。

我们可以填表,来找到状态方程,对于上述例题,填表如下:

ii \  jj 0 1 2 3 4 5 6 7 8 9 10
初始 0 0 0 0 0 0 0 0 0 0 0
w1=2,v1=6w_1=2,v_1=6 0 0 6 6 6 6 6 6 6 6 6
w2=2,v2=3w_2=2,v_2=3 0 0 6 6 9(w1+w2)(w_1+w_2) 9 9 9 9 9 9
w3=6,v3=5w_3=6,v_3=5 0 0 6 6 9 9 9 9 11(w1+w3w_1+w_3) 11 14(w1+w2+w3)(w_1+w_2+w_3)
w4=5,v4=4w_4=5,v_4=4 0 0 6 6 9 9 9 10(w1+w4)(w_1+w_4) 11 13(w1+w2+w4)(w_1+w_2+w_4) 14
w5=4,v5=6w_5=4,v_5=6 0 0 6 6 9 9 12(w1+w5)(w_1+w_5) 12 15(w1+w2+w5)(w_1+w_2+w_5) 15 15
  • dp[2][4] = 9:当背包的容积是 4 时,4 - w[2] = 2,找到之前放入上一个物品时,背包容量为 2 时的最大价值,即 dp[1][2] = 6,故 dp[2][4] = dp[1][2] + v[2] = 6 + 3 = 9
  • dp[3][8] = 11:8 - w[3] = 2,故找到上一次容量为 2 时的最大价值,dp[2][2],故 dp[3][8]= dp[2][2] + v[3] = 6 + 5 = 11
  • dp[3][10] = 14:10 - w[3] = 4,故找到上一次容量为 4 时的最大价值,dp[2][4],故 dp[3][10]= dp[2][4] + v[3] = 9 + 5 =14
  • dp[4][7] = 10:7 - w[4] = 2,故找到上一次容量为2 时的最大价值,dp[3][2],故 dp[4][7]= dp[3][2] + v[4] = 6 + 4 = 10
  • dp[4][9] = 13:9 - w[4] = 4,故找到上一次容量为4 时的最大价值,dp[3][4],故 dp[4][9]= dp[3][4] + v[4] = 9 + 4 = 13
  • dp[5][6] = 12:6 - w[5] = 2,故找到上一次容量为2 时的最大价值,dp[4][2],故 dp[5][6]= dp[4][2] + v[5] = 6 + 6 = 12
  • dp[5][8] = 15:8 - w[5] = 4,故找到上一次容量为4 时的最大价值,dp[4][4],故 dp[5][8]= dp[4][4] + v[5] = 9 + 6 = 15

上述是当放入物品 i 时,能影响到上一次该容量的最大价值的变化,故可以得出规律:dp[i][j] = Max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]),这个就是我们的状态方程。

输入数据

sh 复制代码
5 10
2 6
2 3
6 5
5 4
4 6

输出数据

sh 复制代码
15

初始化细节:

  • 题目如果要求装满背包,即一定没有剩余容量,则初始化 dp[0] = 0,其余赋值 -INF;
  • 如果不要求背包一定要装满,只考虑能最大价值,那么则全部初始化为 0 即可。

若一定要求装满:

  • 则必有 n=sum(c[i]) i∈(已选集合)
  • 所以 dp[n - sum(c[i])]= dp[0]
  • 所以只有从 dp[0] 出发才合法,那就把其他的设成无穷小。

如下:

java 复制代码
// 装满
Arrays.fill(dp, -0x3f3f3f3f);
dp[0] = 0;

// 不装满
for (int i = 0; i <= N; i++) {
	for (int j = 0; j <= C; j++) {
		dp[i][j] = 0;
	}
}

二维DP

那知道思路后,我们可以开始编写代码,题目不要求一定装满,只要求能得到最大价值即可。

java 复制代码
import java.util.*;

public class Main {

	static int[][] dp;

//	static int N = 5;  // n件物品
//	static int C = 10; // 背包容量
//	static int[] w = { 2, 2, 6, 5, 4 };
//	static int[] v = { 6, 3, 5, 4, 6 };
	static int[] w = new int[110]; // 体积
	static int[] v = new int[110]; // 价值

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int C = sc.nextInt(); // 背包容量
		dp = new int[N + 10][C + 10]; // 二维dp
		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		System.out.print(solve(N, C));
	}

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param C 背包容量
	 * @return
	 */
	private static int solve(int N, int C) {
		// 初始化
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= C; j++) {
				dp[i][j] = 0;
			}
		}
		// 从第一个物品开始往下放进背包,看看怎么放最大
		for (int i = 1; i <= N; i++) {
			// 当前物品的体积
			int curW = c[i];
			// 遍历 0 到 C 每种容量情况
			for (int j = 0; j <= C; j++) {
				// 上一个商品组合的价值
				int lastV = dp[i - 1][j];
				// 当前物品放不下,则存放上一次组合的价值
				if (curW > j) {
					dp[i][j] = lastV;
				} else {
					int m = j - curW; // 存放该物品时剩余的体积
					// 找到上一次存放达到这个体积的最大价值,加入该物品
					int curV = dp[i - 1][m] + v[i];
					// 得到最大值
					dp[i][j] = Math.max(curV, lastV);
				}
			}
		}
		return dp[N][C];
	}
}

滚动数组

把 dp[][] 优化成一维的 dp[]。以节省空间。
dp[][] 是从上面一行 dp[i-1] 算出来的,第 i 行只跟第 i-1 行有关系,跟更前面的行没有关系:

java 复制代码
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

优化:只需要两行 dp[0][]、dp[1][],用新的一行覆盖原来的一行,交替滚动。
经过优化,空间复杂度从 O(N×C)O(N\times C) 减少为 0(C)0(C) 。

java 复制代码
import java.util.Scanner;

public class Main {

	static int[][] dp;

//	static int N = 5;  // n件物品
//	static int C = 10; // 背包容量
//	static int[] w = { 2, 2, 6, 5, 4 };
//	static int[] v = { 6, 3, 5, 4, 6 };
	static int[] w = new int[110]; // 体积
	static int[] v = new int[110]; // 价值

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int C = sc.nextInt(); // 背包容量
		dp = new int[N + 10][C + 10]; // 二维dp
		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		System.out.print(solve(N, C));
	}

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param C 背包容量
	 * @return
	 */
	private static int solve(int N, int C) {
		// 初始化
		for (int i = 0; i <= 2; i++) {
			for (int j = 0; j <= C; j++) {
				dp[i][j] = 0;
			}
		}
		for (int i = 1; i <= N; i++) {
			// 交换,将上一次的运算结果 dp[1] 保存到 dp[0]
			System.arraycopy(dp[1], 0, dp[0], 0, C + 1);
			// 当前物品的体积
			int curW = w[i];
			for (int j = 0; j <= C; j++) {
				// 当前容量的背包不足以放入该物品
				if (curW > j) {
					dp[1][j] = dp[0][j];
				} else {
					// 物品尝试与其他物品组合存放,得到当前容量背包的最大价值
					dp[1][j] = Math.max(dp[0][j], dp[0][j - curW] + v[i]);
				}
			}
		}
		return dp[1][C];
	}
}

自我滚动

因为状态转移每次只与上一层有关,所以用一个一维数组就可以。

继续精简:用一个一维的 dp[] 就够了,自己滚动自己。

java 复制代码
dp[j] = dp[j-w[i]] + v[i]

为什么从大到小遍历,看 dp[j]=dp[j - w[i]] + v[i] 这一状态转移,是根据小的改大的,如果先把小的改了,那小的还会被大的用到,数据就不对了,所以从大到小。

java 复制代码
import java.util.*;

public class Main {

	static int[] dp;

//	static int N = 5;  // n件物品
//	static int C = 10; // 背包容量
//	static int[] w = { 2, 2, 6, 5, 4 };
//	static int[] v = { 6, 3, 5, 4, 6 };
	static int[] w = new int[110]; // 体积
	static int[] v = new int[110]; // 价值

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int C = sc.nextInt(); // 背包容量
		dp = new int[C + 10]; // 一维dp
		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		System.out.print(solve(N, C));
	}

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param C 背包容量
	 * @return
	 */
	private static int solve(int N, int C) {
		// 初始化
		Arrays.fill(dp, 0);

		// 从第一个物品开始尝试放进去
		for (int i = 1; i <= N; i++) {
			int curW = w[i];
			// 尝试放入当前 j 容量的背包(这里从大容量开始计算
			// 防止小的先计算后影响大容量的计算
			// 因为状态转移 大容量 dp[j] 的计算依赖上一次小容量 dp[j-curC]
			// 小的先改了,它会被大的用到,数据就有问题,故从大到小
			for (int j = C; j >= curW; j--) {
				// 当前物品放的进容量为j的背包
				// 上一次该体积所存放的最大价值
				int lastV = dp[j];
				// 物品放进背包后剩余的容量的之前所能存放的最大价值+当前物品的价值
				int curV = dp[j - curW] + v[i];
				// 判断上一次的价值与当前物品和其他合适容量物品一起放入谁的价值大
				dp[j] = Math.max(lastV, curV);
			}
		}
		return dp[C];
	}
}

要求装满

那假设题目要求我们装满,这里我用滚动数组来实现,我们初始化的代码需要修改一下,其余思路基本不变,主要是设置一个非常小的值,好判断是否装满。

java 复制代码
import java.util.*;

public class Main {

	static int[][] dp;

//	static int N = 5;  // n件物品
//	static int C = 10; // 背包容量
//	static int[] w = { 2, 2, 6, 5, 4 };
//	static int[] v = { 6, 3, 5, 4, 6 };
	static int[] w = new int[110]; // 体积
	static int[] v = new int[110]; // 价值

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int C = sc.nextInt(); // 背包容量
		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		System.out.print(solve(N, C));
	}

	static int INF = -0x3f3f3f3f;

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param C 背包容量
	 * @return
	 */
	private static int solve(int N, int C) {
		dp = new int[2][C + 1]; // 二维dp
		// 初始化(需要装满背包)
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j <= C; j++) {
				dp[i][j] = INF;
			}
		}
		dp[0][0] = 0; // 用于计算装满情况的值一个状态值
		// 装满的话,当前容量-该物品的容量(或者已选物品的容量加上该物品的容量)= 0
		for (int i = 1; i <= N; i++) {
			// 交换,将上一次的运算结果dp[1]保存到dp[0]
			System.arraycopy(dp[1], 0, dp[0], 0, C + 1);
			dp[0][0] = 0; // 容量为0的情况价值肯定为0
			// 当前物品的体积
			int curW = w[i];
			for (int j = 0; j <= C; j++) {
				// 当前容量的背包不足以放入该物品
				if (curW > j) {
					dp[1][j] = dp[0][j];
				} else {
					// 物品尝试与其他物品组合存放,得到当前容量背包的最大价值
					dp[1][j] = Math.max(dp[0][j], dp[0][j - curW] + v[i]);
				}
			}
		}
		return dp[1][C];
	}
}

可以得到结果与要求不装满的结果不同,为 14,根据我们之前写的表格也可以知道装满的情况为 14,是正确的。

其它例题

装箱问题

原题链接:https://lx.lanqiao.cn/problem.page?gpid=T2102

资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s

问题描述
有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积(正整数)。要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入描述
输入第一行,一个整数,表示箱子容量。
第二行,一个整数 n,表示有 n 个物品。
接下来 n 行,分别表示这 n 个物品的各自体积。

输出描述
输出一行,表示箱子剩余空间。

样例输入

sh 复制代码
24
6
8
3
12
7
9
7

样例输出

sh 复制代码
0

题解

这是一道简单的0/1背包问题,容量与值都是自身,直接套模板即可。

java 复制代码
import java.util.Scanner;

/**
 * 装箱问题
 * https://lx.lanqiao.cn/problem.page?gpid=T2102
 *
 * @author Salmon
 * @since 2024-04-05
 */
public class Main {

    static int[] w = new int[31];

    static int[][] dp = new int[33][20010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        System.out.println(solve(n, v));
    }

    /**
     * * 动态规划
     *
     * @param n 物品个数
     * @param v 箱子容量
     * @return 剩余的空间
     */
    private static int solve(int n, int v) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= v; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            int curV = w[i]; // 当前物品的体积
            // 尝试将该物品放入 0 到 v容积的箱子
            for (int j = 0; j <= v; j++) {
                int lastV = dp[i - 1][j];
                // 当前放不下,则获取上一次的最大值
                if (curV > j) {
                    dp[i][j] = lastV;
                } else {
                    // 放入该物品后的新体积(可能与其它物品组合的体积)
                    int newV = dp[i - 1][j - curV] + w[i];
                    dp[i][j] = Math.max(newV, lastV);
                }
            }
        }
        return v - dp[n][v];
    }
}
image.png

2022

第十三届蓝桥杯C++B组国赛

问题描述
将 2022 拆分成 10 个互不相同的正整数之和,总共有多少种拆分方法?

注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 1022+1000 就视为同一种方法。

答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制
最大运行时间:1s
最大运行内存: 512M

题解

这是一道计数 dp 题。如果实在解决不了,可以考虑暴力枚举法,直接 for 循环 10 层,因为这是一道填空题,不用考虑时间复杂度。答案是:379187662194355221。

java 复制代码
    private static void solve() {
        // 用于去重相同组合
        Set<String> sets = new HashSet<>();
        long start = System.currentTimeMillis();
        long count = 0;
        for (int i = 0; i <= 2022; i++) {
            for (int j = i + 1; i != j && j <= 2022; j++) {
                if (i + j > 2022) {
                    break;
                }
                for (int k = j + 1; i != k && j != k && k <= 2022; k++) {
                    if (i + j + k > 2022) {
                        break;
                    }
                    for (int l = k + 1; i != l && j != l && k != l && l <= 2022; l++) {
                        if (i + j + k + l > 2022) {
                            break;
                        }
                        for (int m = l + 1; i != m && j != m && k != m && l != m && m <= 2022; m++) {
                            if (i + j + k + l + m > 2022) {
                                break;
                            }
                            for (int n = m + 1; i != n && j != n && k != n && l != n && m != n && n <= 2022; n++) {
                                if (i + j + k + l + m + n > 2022) {
                                    break;
                                }
                                for (int o = n + 1; i != o && j != o && k != o && l != o && m != o && n != o && o <= 2022; o++) {
                                    if (i + j + k + l + m + n + o > 2022) {
                                        break;
                                    }
                                    for (int p = o + 1; i != p && j != p && k != p && l != p && m != p && n != p && o != p && p <= 2022; p++) {
                                        if (i + j + k + l + m + n + o + p > 2022) {
                                            break;
                                        }
                                        for (int q = p + 1; i != q && j != q && k != q && l != q && m != q && n != q && o != q && p != q && q <= 2022; q++) {
                                            if (i + j + k + l + m + n + o + p + q > 2022) {
                                                break;
                                            }
                                            for (int r = q + 1; i != r && j != r && k != r && l != r && m != r && n != r && o != r && p != r && q != r && r <= 2022; r++) {
                                                if (i + j + k + l + m + n + o + p + q + r == 2022) {
                                                    int[] arr = {i, j, k, l, m, n, o, p, q, r};
                                                    Arrays.sort(arr);
                                                    if (sets.contains(Arrays.toString(arr))) {
                                                        continue;
                                                    }
                                                    count++;
                                                    sets.add(Arrays.toString(arr));
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        System.out.println(count);
        long end = System.currentTimeMillis();
        System.out.println("耗时:" + (end - start) / 1000 + "s");
    }

下边使用 dp 来解决这个问题,其实就是一个0/1背包问题,可以看成物品的体积为 1 到 2022,选取 10 个 物品,放入容积为 2022 的背包中,要求放满背包,则一共有多少种方案。

定义dp[][][]:dp[i][j][k]表示从 1 到 i 个数字中选取 j 个数字,组合成和为 k 的方案数。

比如:dp[0][0][0]:表示不选择任何数字,组合成和 0 的情况,那这种情况只有一种方案数。

dp[1][0][1]也同理。只有一种方案数。dp[1][1][1],则表示选取一个数字1,组合成和为 1 的方案数,显然也是只有一种可能。

dp[3][2][5],表示选取数字 3,与其余 1 个数字(2-1),组合成和为5的方案数;如果知道上一次未放入 3 时,和为 2 的方案数有多少种,也就是 dp[2][1][2],那在此基础上加入 3,就得到选取2个数字时,和为 5 有多少种方案,除此之外,还要加上原本不选择数字 3 时,同样是选 2个数字,和为 5 的方案数。它们的和就是选择 2 个数字(3 与其它数字 或者 不包含 3 的其它 2 个数字),的和为5的方案数。

那大致了解每一维的作用后,对于选取数字 i 时,我们要分两种情况。

  1. k>=i 时。我们是否选择数字 i。
    1. 要放入 i。从 1 ~ i-1 中取 j-1 个数的方案数中,放入 i,等价于 dp[i-1][j-1][k-i];
    2. 不放入 i。则从 1 ~ i-1 个数字中,取 j 个数的方案数。等价于 dp[i-1][j][k]。
  2. k<i 时。由于数字 i 比总和 k 还大,显然 i 不能用,则保留它的方案数为上一次没有加入 i 时的方案数。dp[i-1][j][k]。

注意初始化细节:dp[i][0][0]=1,选到i个数,选0个数进行组合,和为0的方案数,只有一种,表示什么都没选的情况。

为什么 dp[i][j>0][0]不初始化为1呢?
选择多个数(1 ~ i),组合成和为 0 的情况不存在。故 dp[i][j>0][0] = 0。

为什么 dp[i][0][k>0]不初始化为1呢?
选择 0 个数,和为 k 的情况,也不存在。故 dp[i][0][k>0] = 0。

java 复制代码
public class Main {

    // 存储方案数
    static long[][][] dp = new long[2023][11][2023];

    public static void main(String[] args) {
        solve(10, 2023);
    }


    /**
     * 动态规划解决
     *
     * @param partNum   拆分个数
     * @param targetNum 被拆分数
     */
    private static void solve(int partNum, int targetNum) {
        // 不使用任何数字的和为0,那么它的方案就只有一种,什么都没选。
        dp[0][0][0] = 1;
        // 遍历待选择的数字 1 到 2022,计算每个数字使用 j 个数字组合成和为 k 的方案数
        for (int i = 1; i <= targetNum; i++) {
            // 不使用任何数字的和为0,那么它的方案就只有一种,什么都没选。
            dp[i][0][0] = 1;
            // 10个物品,对应的是10个不同的数字
            for (int j = 0; j <= partNum; j++) {
                // 遍历从 0 - k,求 0 - k 每个数字的 j 种方案数有多少
                for (int k = 1; k <= targetNum; k++) {
                    // 如果当前要加入组合的数 i 大于 k
                    // 则当前这个数字 i 不可能被组合成 k
                    if (i > k) {
                        // 故对于当前这个组合数为j,和为k的方案数,与之前不使用i时相同
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        // 不使用任何数字时,则与不使用 i 时的情况相同
                        if (j == 0) {
                            dp[i][j][k] = dp[i - 1][j][k];
                        } else {
                            // 至少选一个数(i 本身)
                            // 查找使用 j-1 个数字(不包括当前数字 i)组合成和为 k-i 的方案数
                            // 然后加入我们放入的数字 i,不就相当于在之前的组合情况基础上加了一个数字 i
                            // 那么组合数其实就与没加i之前一样
                            dp[i][j][k] = dp[i - 1][j - 1][k - i];

                            // 将不使用当前数字 i,而是使用前一个数字 i-1 时,
                            // 用 j 个数字组合成和为k的方案数累加上去
                            dp[i][j][k] += dp[i - 1][j][k];
                        }
                    }
                }
            }
        }
        System.out.println(dp[targetNum][partNum][targetNum]);
    }
}

我们可以观察到,我们只是需要得到 i-1 的结果,而不需要其它结果,我们可以降成二维 dp。如下:

java 复制代码
public class Main {

    // 存储方案数
    static long[][] dp = new long[11][2023];

    public static void main(String[] args) {
        solve(10, 2022);
    }

    /**
     * 动态规划解决(滚动数组,降成二维)
     *
     * @param partNum   拆分个数
     * @param targetNum 被拆分数
     */
    private static void solve(int partNum, int targetNum) {
        dp1[0][0] = 1;
        for (int i = 1; i <= targetNum; i++) {
            // 大拆分的结果依赖于上一次的子拆分的结果,故得先处理大的值,防止被覆盖
            for (int j = partNum; j >= 1; j--) {
                // 和至少是包含 i 的情况,不包含 i 的情况保持上一次的结果即可
                for (int k = i; k <= 2022; k++) {
                    dp[j][k] = dp[j][k] + dp[j - 1][k - i];
                }
            }
        }
        System.out.println(dp1[partNum][targetNum]);
    }
}

完全背包

解题思路和 0/1 背包类似。0/1 背包的每种物品只有1件,完全背包的每种物品有无穷多件,第 i 种 可以装 0 件、1 件、C/ci 件。

定义 dp[i][j]:把前 i 种物品(从第 1 种到第 i 种)转入容量为 j 的背包中获得的最大价值。

把每个 dp[i][j] 都看成一个背包:背包容量为 j,装 1 ~ i 这些物品。最后得到的 dp[N][C] 就是问题的答案:把 N 种物品装进容量为 C 的背包的最佳价值。

在 0/1 背包问题中,每个物品只有拿与不拿两种;而完全背包问题,需要考虑几个。

例子

有 5 个物品,重量分别是{3,2,1,5,3}, 价值分别为{8,5,6,15,3},背包的容量为 10。每个物品有无穷个。求背包可以装得物品的最大价值。

分析

我们依旧可以填表,来找到状态方程。

ii \  jj 0 1 2 3 4 5 6 7 8 9 10
初始 0 0 0 0 0 0 0 0 0 0 0
w1=3,v1=8w_1=3,v_1=8 0 0 0 8 8 8 16(2∗w12*w_1) 16 16 24(3∗w13*w_1) 24
w2=2,v2=5w_2=2,v_2=5 0 0 5 8 10(2∗w22*w_2) 13(w1+w2w_1+w_2) 16 18(w1+2∗w2w_1+2*w_2) 21(2∗w1+w22*w_1+w_2) 24 26(2∗w1+2∗w22*w_1+2*w_2)
w3=1,v3=6w_3=1,v_3=6 0 6 12(2∗w32*w_3) 18(3∗w33*w_3) 24(4∗w34*w_3) 30(5∗w35*w_3) 36(6∗w36*w_3) 42(7∗w37*w_3) 48(8∗w38*w_3) 54(9∗w39*w_3) 60(10∗w310*w_3)
w4=5,v4=15w_4=5,v_4=15 0 6 12 18 24 30 36 42 48 54 60
w5=3,v5=3w_5=3,v_5=3 0 6 12 18 24 30 36 42 48 54 60

处理完全背包问题,我们需要考虑放入同件物品 i,而我们 dp 存储的是当时容量 j 最优的情况。故可以分为两种情况讨论,dp[i][j] 的取值:

  • 不选 i 时,则取上一次对于容量 j 最优的情况,dp[i][j] = dp[i-1][j];
  • 选 i 时,如果只是 0/1 背包,则考虑在之前未选择 i,选 1 件 i 后,对于容量 j 能不能获得更好的情况,故为 Math.max(dp[i - 1][j - w[i]] + v[i], dp[i-1][j])。而对于完全背包问题,同一件物品能选择多件,我们则需多考虑一个情况,即这时我们选择了 i 后,放下 i 背包剩余容积 j - w[i] 的最优情况。
    • 这个情况有未选择 i 时能存放的最大价值(dp[i - 1][j - w[i]]);
    • 以及之前选择 i 后,所存放的最大价值,即dp[i][j - w[i]],而由于之前处理 dp[i][j - w[i]] 存放的就是当时的最有情况(无 i 或者 有 1 个或多个 i 时的最优情况)。故我们选择 1 个或多个 i 时, dp[i][j] = Math.max(dp[i][j - w[i]] + v[i], dp[i-1][j])

所以状态方程为 dp[i][j] = Math.max(dp[i][j - w[i]] + v[i], dp[i-1][j]),简单理解就是:每次对于处理容积 j 的情况时,只要背包能放的下物品 i,就会去尝试放入它,看看放入第 k 个 i 的情况与不放入的情况,哪个是最优解。

如上述表格中,dp[2][4]:假设第 2 个物品叫 B。这个状态相当于在背包容量为 4,选择第二件物品 B,而物品 B 的体积才 2,故我们看看之前背包容量为在 4 - 2 = 2 的最优情况,即 dp[2][2],而这个最优情况刚好是当时放入第 1 个物品时产生的。但同时,我们还得看看不选择放入物品 B 时,也就是上一次该容量的最优情况,是否能让 dp[2][4]取得最优解,但这里很显然上一次的没选择 B 时,容量为 4 的背包的最优情况为 8,而我们放入 B,容量为 4 的背包的价值为 10,那么肯定去最优情况为 10,也就是放入两个物品 B 的情况是最优解。

输入数据

sh 复制代码
5 10
1 6
2 5
3 8
5 15
3 3

输出数据

sh 复制代码
60

二维DP

理解后,我们可以写代码:

java 复制代码
import java.util.*;

public class Main {

	static int[][] dp = new int[1010][1010];
	static int[] w = new int[1010];
	static int[] v = new int[1010];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int V = sc.nextInt(); // 背包容量

		// 初始化
		Arrays.fill(dp[0], 0);

		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
			// 顺便初始化
			Arrays.fill(dp[i], 0);
		}
		System.out.print(solve(N, V));
	}

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param V 背包容量
	 * @return
	 */
	private static int solve(int N, int V) {
		// 遍历每个物品,尝试放入背包中
		for (int i = 1; i <= N; i++) {
			int curW = w[i]; // 物品体积
			int curV = v[i]; // 物品价值
			// 遍历放进每种背包容量的情况,计算对于这种容量的最优解
			for (int j = 1; j <= V; j++) {
				// 不选择放入物品,则背包的价值与上一次相同
				dp[i][j] = dp[i - 1][j];
				// 如果背包容量足够,选1个或者多个(直接取当前放入 i 后,剩余容积在当时在选择 i 时的最优解)
				if (j >= curW) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - curW] + curV);
				}
			}
		}
		return dp[N][V];
	}
}

自我滚动

我们每一躺只与当前这一趟与上一趟的结果有关系,故我们可以空间压缩成一维。注意,与 0/1 背包问题不同的是,完全背包问题在处理每个容积的情况时,选取的是有考虑到物品 i 的结果的最优解,而不是为未考虑物品 i 的最优解,故我们要覆盖掉之前未考物品 i 的最优解。

java 复制代码
import java.util.*;

public class Main {

	static int[] dp = new int[1010];
	static int[] w = new int[1010];
	static int[] v = new int[1010];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // n件物品
		int V = sc.nextInt(); // 背包容量

		// 初始化
		Arrays.fill(dp, 0);

		for (int i = 1; i <= N; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		System.out.print(solve(N, V));
	}

	/**
	 * 动态规划
	 * 
	 * @param N 物品个数
	 * @param V 背包容量
	 * @return
	 */
	private static int solve(int N, int V) {
		// 遍历每个物品,尝试放入背包中
		for (int i = 1; i <= N; i++) {
			int curW = w[i]; // 物品体积
			int curV = v[i]; // 物品价值
			// 开始存放物品,我们希望当前选择i后的结果能被保留
			// 注意从小到大遍历
			for (int j = curW; j <= V; j++) {
				dp[j] = Math.max(dp[j], dp[j - curW] + curV);
			}
		}
		return dp[V];
	}
}

多重背包问题

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句