国家高新技术企业税收优惠政策,惠州网站建设乐云seo在线制作,桂林建站,东莞网站建设 塑胶五金文章目录 题面基本的01背包问题本题变式 本文参考#xff1a; 9.10拼多多笔试ak_牛客网 (nowcoder.com) 拼多多 秋招 2023.09.10 编程题目与题解 (xiaohongshu.com) 题面
拼多多9.10笔试的最后一题#xff0c;是一道比较好的01背包变式问题#xff0c;可以学习其解法加深对… 文章目录 题面基本的01背包问题本题变式 本文参考 9.10拼多多笔试ak_牛客网 (nowcoder.com) 拼多多 秋招 2023.09.10 编程题目与题解 (xiaohongshu.com) 题面
拼多多9.10笔试的最后一题是一道比较好的01背包变式问题可以学习其解法加深对01背包问题的理解。
这是拼多多2023-9-10秋招笔试的第四题数据量不大甚至可以通过dfs暴力穷举写出来每个部件只有修和换两种选择总共就是2^NN40的复杂度理论上来说这个复杂度是很危险的但有题友也做出来了。当时自己也是有畏难心理甚至没有去尝试写dfs导致这题0分下次多少得先尝试一下。
可是dfs终究是没那么优雅这题其实可以巧妙地转换为背包问题。初次尝试时也确实往背包问题考虑了但是想想一个维度为修车部件N一个维度为修车时间M并且题目要求无论是修还是换这些部件全部都得处理好也就是物品要被“全部选取”一般的背包问题好像没法往“全部选择”这上面靠基本思想都是在有限的容量下达成价值的最大而选出来物品是“部分选择”出来的。
基本的01背包问题
一个基本的01背包问题如下
在背包容量为4的情况下选择价值最大的物品组合。
从打印的答案中也可以看出最后只选择了1520这两件物品。
/*** 每件物品只能取一次* 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][maxBag1];// 初始化这里maxBag1留下maxBag0的空间方便偷懒递归后续背包容量dp[0][]偷懒指定第一个物品// 倒序初始化保证每个物品只会被选取一次for (int j maxBag; j0; 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; j0; 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; jmaxBag; 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背包对于物品ivalues[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][maxBag1];// 倒序初始化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; iN; i){for (int j maxBag; j0; 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);}
}
