从9.10拼多多笔试第四题产生的01背包感悟

本文参考：

9.10拼多多笔试ak_牛客网 (nowcoder.com)

拼多多 秋招 2023.09.10 编程题目与题解 (xiaohongshu.com)

题面

拼多多9.10笔试的最后一题，是一道比较好的01背包变式问题，可以学习其解法加深对01背包问题的理解。

这是拼多多2023-9-10秋招笔试的第四题，数据量不大，甚至可以通过dfs暴力穷举写出来，每个部件只有修和换两种选择，总共就是2^N（N<=40）的复杂度，理论上来说这个复杂度是很危险的，但有题友也做出来了。当时自己也是有畏难心理，甚至没有去尝试写dfs，导致这题0分，下次多少得先尝试一下。

可是dfs终究是没那么优雅，这题其实可以巧妙地转换为背包问题。初次尝试时也确实往背包问题考虑了，但是想想一个维度为修车部件N，一个维度为修车时间M，并且题目要求无论是修还是换，这些部件全部都得处理好，也就是物品要被“全部选取”，一般的背包问题好像没法往“全部选择”这上面靠，基本思想都是在有限的容量下达成价值的最大，而选出来物品是“部分选择”出来的。

基本的01背包问题

一个基本的01背包问题如下：

在背包容量为4的情况下，选择价值最大的物品组合。

从打印的答案中也可以看出，最后只选择了15，20这两件物品。

/*** 每件物品只能取一次* @Author jiangxuzhao* @Description* @Date 2023/9/10*/
public class bag01 {public static void main(String[] args) {// 物品价值和成本int[] values = {15, 20, 30};int[] costs = {1, 3, 4};// 背包最多装4int maxBag = 4;// 物品数量int len = costs.length;// dp[i][j]表示从下标为[0,i]物品中选择，放进容量为j的背包中能产生的最大价值// 整体空间根据物品-背包容量排开int[][] dp = new int[len][maxBag+1];// 初始化，这里maxBag+1留下maxBag=0的空间，方便偷懒递归后续背包容量，dp[0][]偷懒指定第一个物品// 倒序初始化保证每个物品只会被选取一次for (int j = maxBag; j>=0; j--){if (j >= costs[0]) {dp[0][j] = dp[0][j-costs[0]] + values[0];}}// 递推公式，本次物品选或者不选for (int i = 1; i < len; i++){// 倒序遍历背包容量保证每个物品只会被选取一次for (int j = maxBag; j>=0; j--){// 不选本次物品idp[i][j] = dp[i-1][j];// 选择本次物品iif (j >= costs[i]) {dp[i][j] = Math.max(dp[i][j], dp[i-1][j-costs[i]]+values[i]);}}}// 结果打印for (int i = 0; i < len; i++){for (int j = 0; j<=maxBag; j++){System.out.print(dp[i][j]+" ");}System.out.println();}}
}

本题变式

提示:这题确实也可以用01背包来做，但是需要经过一层转换。

这里需要求的是在M时间内修好自行车，再去看要的最少金钱，那么首先要检查不计成本，最少时间的情况下是否可以修好自行车，也就是将所有“换部件”的时间累加，判断是否大于M，如果不超过M，则还有降低成本的空间。

假设上面所有“换部件”的累加时间为leastTime，那么M-leastTime就是我们还能够去多花费的缓冲时间，考虑部件i，如果换成“修部件”，在原先的基础上，时间成本增加Ai - Ci，可以减少Di - Bi的成本。这其实就可以转换成01背包问题了，首先在“全部换”的基础上，起码能保证物品能够被“全部选择处理”，然后n个部件中，如果选择“修”，能够多花的总时间容量为M-t，第i个物品修理多花费的时间是Ai-Ci，能减少Di - Bi的成本，求一个“选择处理的修组合”来最大减少成本，保证花钱最少。

最终编码如下：

import java.util.Scanner;/*** 输入样例* 1 10* 10 2 3 5* 输出样例* 2* 输入样例* 1 10* 12 2 3 5* 输出样例* 5* 输入样例* 1 10* 10 2 3 5* 输出样例* 2* @Author jiangxuzhao* @Description* @Date 2023/9/12*/
public class Pdd_9_10_D {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();// 全部换的时间long leastTime = 0L;// 全部换的成本long maxCost = 0L;// 类比01背包，对于物品i，values[i]为可以减少的成本，costs[i]为多花费的时间int[] values = new int[N];int[] costs = new int[N];for(int i = 0; i < N; i++) {// 修时间int Ai = sc.nextInt();// 修成本int Bi = sc.nextInt();// 换时间int Ci = sc.nextInt();// 换成本int Di = sc.nextInt();leastTime += Ci;maxCost += Di;values[i] = Di - Bi;costs[i] = Ai - Ci;}if (leastTime > M){System.out.println(-1);return;}// 最大背包容量 = 多花费的缓冲时间int maxBag = (int)(M - leastTime);// 最大背包价值 = 选择处理的修组合最大减少成本long bagRes = 0L;long[][] dp = new long[N][maxBag+1];// 倒序初始化for(int j = maxBag; j >= 0; j--){if(j >= costs[0]) dp[0][j] = dp[0][j-costs[0]] + values[0];}for (int i = 1; i<N; i++){for (int  j = maxBag; j>=0; j--){// 不选当前物品dp[i][j] = dp[i-1][j];// 选当前物品dp[i][j] = Math.max(dp[i][j], dp[i-1][j-costs[i]]+values[i]);}}bagRes = dp[N-1][maxBag];// 最少花费的金钱long res = maxCost - bagRes;System.out.println(res);}
}