class073 背包dp-01背包、有依赖的背包【算法】

class073 背包dp-01背包、有依赖的背包【算法】

算法讲解073【必备】背包dp-01背包、有依赖的背包

在这里插入图片描述

code1 P1048 [NOIP2005 普及组] 采药

// 01背包(模版)
// 给定一个正数t，表示背包的容量
// 有m个货物，每个货物可以选择一次
// 每个货物有自己的体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1048
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

dp[i][j]：编号1…i的物品自由选择，容量不超过j的最大价值
①不要i号物品，dp[i-1][j]
②要i号物品,dp[i-1][j-cost[i]]+val[i]，注意j-cost[i]不能是负数
二者取较大值

第0行：0
返回dp[n][t]

package class073;// 01背包(模版)
// 给定一个正数t，表示背包的容量
// 有m个货物，每个货物可以选择一次
// 每个货物有自己的体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1048
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Code01_01Knapsack {public static int MAXM = 101;public static int MAXT = 1001;public static int[] cost = new int[MAXM];public static int[] val = new int[MAXM];public static int[] dp = new int[MAXT];public static int t, n;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {t = (int) in.nval;in.nextToken();n = (int) in.nval;for (int i = 1; i <= n; i++) {in.nextToken();cost[i] = (int) in.nval;in.nextToken();val[i] = (int) in.nval;}out.println(compute2());}out.flush();out.close();br.close();}// 严格位置依赖的动态规划// n个物品编号1~n，第i号物品的花费cost[i]、价值val[i]// cost、val数组是全局变量，已经把数据读入了public static int compute1() {int[][] dp = new int[n + 1][t + 1];for (int i = 1; i <= n; i++) {for (int j = 0; j <= t; j++) {// 不要i号物品dp[i][j] = dp[i - 1][j];if (j - cost[i] >= 0) {// 要i号物品dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost[i]] + val[i]);}}}return dp[n][t];}// 空间压缩public static int compute2() {Arrays.fill(dp, 0, t + 1, 0);for (int i = 1; i <= n; i++) {for (int j = t; j >= cost[i]; j--) {dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);}}return dp[t];}}

code2 bytedance-006. 夏季特惠

// 夏季特惠
// 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏
// 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣
// 标号为 i 的游戏的原价a_i元，现价只要b_i元
// 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
// 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算
// 只要满足 : 获得的总优惠金额不低于超过预算的总金额
// 那在心理上就不会觉得吃亏。
// 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
// 测试链接 : https://leetcode.cn/problems/tJau2o/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

package class073;// 夏季特惠
// 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏
// 现在你一共有X元的预算，平台上所有的 n 个游戏均有折扣
// 标号为 i 的游戏的原价a_i元，现价只要b_i元
// 也就是说该游戏可以优惠 a_i - b_i，并且你购买该游戏能获得快乐值为w_i
// 由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算
// 只要满足 : 获得的总优惠金额不低于超过预算的总金额
// 那在心理上就不会觉得吃亏。
// 现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
// 测试链接 : https://leetcode.cn/problems/tJau2o/
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Code02_BuyGoodsHaveDiscount {public static int MAXN = 501;public static int MAXX = 100001;// 对于"一定要买的商品"，直接买！// 只把"需要考虑的商品"放入cost、val数组public static int[] cost = new int[MAXN];public static long[] val = new long[MAXN];public static long[] dp = new long[MAXX];public static int n, m, x;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;m = 1;in.nextToken();x = (int) in.nval;long ans = 0;long happy = 0;for (int i = 1, pre, cur, well; i <= n; i++) {// 原价in.nextToken(); pre = (int) in.nval;// 现价in.nextToken(); cur = (int) in.nval;// 快乐值in.nextToken(); happy = (long) in.nval;well = pre - cur - cur;// 如下是一件"一定要买的商品"// 预算 = 100，商品原价 = 10，打折后 = 3// 那么好处(well) = (10 - 3) - 3 = 4// 所以，可以认为这件商品把预算增加到了104！一定要买！// 如下是一件"需要考虑的商品"// 预算 = 104，商品原价 = 10，打折后 = 8// 那么好处(well) = (10 - 8) - 8 = -6// 所以，可以认为这件商品就花掉6元！// 也就是说以后花的不是打折后的值，是"坏处"if (well >= 0) {x += well;ans += happy;} else {cost[m] = -well;val[m++] = happy;}}ans += compute();out.println(ans);}out.flush();out.close();br.close();}public static long compute() {Arrays.fill(dp, 0, x + 1, 0);for (int i = 1; i <= m; i++) {for (int j = x; j >= cost[i]; j--) {dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);}}return dp[x];}}

code3 494. 目标和

// 目标和
// 给你一个非负整数数组 nums 和一个整数 target 。
// 向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数
// 可以构造一个表达式
// 例如nums=[2, 1]，可以在2之前添加’+’ ，在1之前添加’-’
// 然后串联起来得到表达式 “+2-1” 。
// 返回可以通过上述方法构造的，运算结果等于 target 的不同表达式的数目
// 测试链接 : https://leetcode.cn/problems/target-sum/

划分为A B两集合
sumA-sumB=target
sumB=sum-sumA
sumA=(target+sum)/2

code1 递归
code2 记忆化搜索
code3 动态规划
code4 01背包

package class073;import java.util.HashMap;// 目标和
// 给你一个非负整数数组 nums 和一个整数 target 。
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数
// 可以构造一个表达式
// 例如nums=[2, 1]，可以在2之前添加'+' ，在1之前添加'-'
// 然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的，运算结果等于 target 的不同表达式的数目
// 测试链接 : https://leetcode.cn/problems/target-sum/
public class Code03_TargetSum {// 普通尝试，暴力递归版public static int findTargetSumWays1(int[] nums, int target) {return f1(nums, target, 0, 0);}// nums[0...i-1]范围上，已经形成的累加和是sum// nums[i...]范围上，每个数字可以标记+或者-// 最终形成累加和为target的不同表达式数目public static int f1(int[] nums, int target, int i, int sum) {if (i == nums.length) {return sum == target ? 1 : 0;}return f1(nums, target, i + 1, sum + nums[i]) + f1(nums, target, i + 1, sum - nums[i]);}// 普通尝试，记忆化搜索版public static int findTargetSumWays2(int[] nums, int target) {// i, sum -> value（返回值 ）HashMap<Integer, HashMap<Integer, Integer>> dp = new HashMap<>();return f2(nums, target, 0, 0, dp);}// 因为累加和可以为负数// 所以缓存动态规划表用哈希表public static int f2(int[] nums, int target, int i, int j, HashMap<Integer, HashMap<Integer, Integer>> dp) {if (i == nums.length) {return j == target ? 1 : 0;}if (dp.containsKey(i) && dp.get(i).containsKey(j)) {return dp.get(i).get(j);}int ans = f2(nums, target, i + 1, j + nums[i], dp) + f2(nums, target, i + 1, j - nums[i], dp);dp.putIfAbsent(i, new HashMap<>());dp.get(i).put(j, ans);return ans;}// 普通尝试// 严格位置依赖的动态规划// 平移技巧public static int findTargetSumWays3(int[] nums, int target) {int s = 0;for (int num : nums) {s += num;}if (target < -s || target > s) {return 0;}int n = nums.length;// -s ~ +s -> 2 * s + 1int m = 2 * s + 1;// 原本的dp[i][j]含义:// nums[0...i-1]范围上，已经形成的累加和是sum// nums[i...]范围上，每个数字可以标记+或者-// 最终形成累加和为target的不同表达式数目// 因为sum可能为负数，为了下标不出现负数，// "原本的dp[i][j]"由dp表中的dp[i][j + s]来表示// 也就是平移操作！// 一切"原本的dp[i][j]"一律平移到dp表中的dp[i][j + s]int[][] dp = new int[n + 1][m];// 原本的dp[n][target] = 1，平移！dp[n][target + s] = 1;for (int i = n - 1; i >= 0; i--) {for (int j = -s; j <= s; j++) {if (j + nums[i] + s < m) {// 原本是 : dp[i][j] = dp[i + 1][j + nums[i]]// 平移！dp[i][j + s] = dp[i + 1][j + nums[i] + s];}if (j - nums[i] + s >= 0) {// 原本是 : dp[i][j] += dp[i + 1][j - nums[i]]// 平移！dp[i][j + s] += dp[i + 1][j - nums[i] + s];}}}// 原本应该返回dp[0][0]// 平移！// 返回dp[0][0 + s]return dp[0][s];}// 新思路，转化为01背包问题// 思考1:// 虽然题目说nums是非负数组，但即使nums中有负数比如[3,-4,2]// 因为能在每个数前面用+或者-号// 所以[3,-4,2]其实和[3,4,2]会达成一样的结果// 所以即使nums中有负数，也可以把负数直接变成正数，也不会影响结果// 思考2:// 如果nums都是非负数，并且所有数的累加和是sum// 那么如果target>sum，很明显没有任何方法可以达到target，可以直接返回0// 思考3:// nums内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性// 所以，如果所有数的累加和是sum，并且与target的奇偶性不一样// 那么没有任何方法可以达到target，可以直接返回0// 思考4(最重要):// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3// 其中一个方案是 : +1 -2 +3 -4 +5 = 3// 该方案中取了正的集合为A = {1，3，5}// 该方案中取了负的集合为B = {2，4}// 所以任何一种方案，都一定有 sum(A) - sum(B) = target// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)// 2 * sum(A) = target + 数组所有数的累加和// sum(A) = (target + 数组所有数的累加和) / 2// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2// 那么就一定对应一种target的方式// 比如非负数组nums，target = 1, nums所有数累加和是11// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6// 因为，子集累加和6 - 另一半的子集累加和5 = 1（target)// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量// 至此已经转化为01背包问题了public static int findTargetSumWays4(int[] nums, int target) {int sum = 0;for (int n : nums) {sum += n;}if (sum < target || ((target & 1) ^ (sum & 1)) == 1) {return 0;}return subsets(nums, (target + sum) >> 1);}// 求非负数组nums有多少个子序列累加和是t// 01背包问题(子集累加和严格是t) + 空间压缩// dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]public static int subsets(int[] nums, int t) {if (t < 0) {return 0;}int[] dp = new int[t + 1];dp[0] = 1;for (int num : nums) { // i省略了for (int j = t; j >= num; j--) {dp[j] += dp[j - num];}}return dp[t];}}

code4 1049. 最后一块石头的重量 II

// 最后一块石头的重量 II
// 有一堆石头，用整数数组 stones 表示
// 其中 stones[i] 表示第 i 块石头的重量。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎
// 假设石头的重量分别为 x 和 y，且 x <= y
// 那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x
// 最后，最多只会剩下一块 石头，返回此石头 最小的可能重量
// 如果没有石头剩下，就返回 0
// 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/

划分为A B两集合
划分为A B两集合
abs(sumA-sumB)小
sumB=sum-sumA
sumA与sum/2最接近

dp[i][j]：前i个数不超过j的最接近累加和
①dp[i-1][j]
②dp[i-1][j-nums[i]]+nums[i]
两者取较大值

package class073;// 最后一块石头的重量 II
// 有一堆石头，用整数数组 stones 表示
// 其中 stones[i] 表示第 i 块石头的重量。
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎
// 假设石头的重量分别为 x 和 y，且 x <= y
// 那么粉碎的可能结果如下：
// 如果 x == y，那么两块石头都会被完全粉碎；
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x
// 最后，最多只会剩下一块 石头，返回此石头 最小的可能重量
// 如果没有石头剩下，就返回 0
// 测试链接 : https://leetcode.cn/problems/last-stone-weight-ii/
public class Code04_LastStoneWeightII {public static int lastStoneWeightII(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}// nums中随意选择数字// 累加和一定要 <= sum / 2// 又尽量接近int near = near(nums, sum / 2);return sum - near - near;}// 非负数组nums中，子序列累加和不超过t，但是最接近t的累加和是多少// 01背包问题(子集累加和尽量接近t) + 空间压缩public static int near(int[] nums, int t) {int[] dp = new int[t + 1];for (int num : nums) {for (int j = t; j >= num; j--) {// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])dp[j] = Math.max(dp[j], dp[j - num] + num);}}return dp[t];}}

code5 购物单

// 有依赖的背包(模版)
// 物品分为两大类：主件和附件
// 主件的购买没有限制，钱够就可以；附件的购买有限制，该附件所归属的主件先购买，才能购买这个附件
// 例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件
// 以下是一些主件及其附件的展示：
// 电脑：打印机，扫描仪 | 书柜：图书 | 书桌：台灯，文具 | 工作椅：无附件
// 每个主件最多有2个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以
// 所有的物品编号都在1~m之间，每个物品有三个信息：价格v、重要度p、归属q
// 价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件
// 比如一件商品信息为[300,2,6]，花费300，收益600，该商品是6号主件商品的附件
// 再比如一件商品信息[100,4,0]，花费100，收益400，该商品自身是主件(q==0)
// 给定m件商品的信息，给定总钱数n，返回在不违反购买规则的情况下最大的收益
// 测试链接 : https://www.luogu.com.cn/problem/P1064
// 测试链接 : https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

king数组：表示是否是主商品
fans数组：附件数量
followss数组：附件编号数组

dp[i][j]：0…i范围上，只关心主商品，并且进行展开,花费不超过j的情况下，获得的最大收益
情况1：不要该主商品，dp[p][j]，p是上一个主商品的编号
情况2：只要主商品，dp[p][j-cost[i]]+val[i]
有附件的情况下考虑：
情况3：要主商品，要附件1，dp[p][j-cost[i]-cost[fan1]]+val[i]，j-cost[i]-cost[fan1]>=0
情况4：要主商品，要附件2，dp[p][j-cost[i]-cost[fan2]]+val[i]，j-cost[i]-cost[fan2]>=0
情况5：要主商品，要附件1和2，dp[p][j-cost[i]-cost[fan1]-cost[fan2]]+val[i]，j-cost[i]-cost[fan1]-cost[fan2]>=0
所有情况下选最大值。

0行：无商品的时候，无收益，为0
返回：dp[p][i]，最后一件主键商品展开后的最大收益。

package class073;// 有依赖的背包(模版)
// 物品分为两大类：主件和附件
// 主件的购买没有限制，钱够就可以；附件的购买有限制，该附件所归属的主件先购买，才能购买这个附件
// 例如，若想买打印机或扫描仪这样的附件，必须先购买电脑这个主件
// 以下是一些主件及其附件的展示：
// 电脑：打印机，扫描仪 | 书柜：图书 | 书桌：台灯，文具 | 工作椅：无附件
// 每个主件最多有2个附件，并且附件不会再有附件，主件购买后，怎么去选择归属附件完全随意，钱够就可以
// 所有的物品编号都在1~m之间，每个物品有三个信息：价格v、重要度p、归属q
// 价格就是花费，价格 * 重要度 就是收益，归属就是该商品是依附于哪个编号的主件
// 比如一件商品信息为[300,2,6]，花费300，收益600，该商品是6号主件商品的附件
// 再比如一件商品信息[100,4,0]，花费100，收益400，该商品自身是主件(q==0)
// 给定m件商品的信息，给定总钱数n，返回在不违反购买规则的情况下最大的收益
// 测试链接 : https://www.luogu.com.cn/problem/P1064
// 测试链接 : https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Code05_DependentKnapsack {public static int MAXN = 33001;public static int MAXM = 61;public static int[] cost = new int[MAXM];public static int[] val = new int[MAXM];public static boolean[] king = new boolean[MAXM];public static int[] fans = new int[MAXM];public static int[][] follows = new int[MAXM][2];public static int[] dp = new int[MAXN];public static int n, m;public static void clean() {for (int i = 1; i <= m; i++) {fans[i] = 0;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StreamTokenizer in = new StreamTokenizer(br);PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));while (in.nextToken() != StreamTokenizer.TT_EOF) {n = (int) in.nval;in.nextToken();m = (int) in.nval;clean();for (int i = 1, v, p, q; i <= m; i++) {in.nextToken(); v = (int) in.nval;in.nextToken(); p = (int) in.nval;in.nextToken(); q = (int) in.nval;cost[i] = v;val[i] = v * p;king[i] = q == 0;if (q != 0) {follows[q][fans[q]++] = i;}}out.println(compute2());}out.flush();out.close();br.close();}// 严格位置依赖的动态规划public static int compute1() {// dp[0][....] = 0 : 无商品的时候int[][] dp = new int[m + 1][n + 1];// p : 上次展开的主商品编号int p = 0;for (int i = 1, fan1, fan2; i <= m; i++) {if (king[i]) {for (int j = 0; j <= n; j++) {// dp[i][j] : 0...i范围上，只关心主商品，并且进行展开//            花费不超过j的情况下，获得的最大收益// 可能性1 : 不考虑当前主商品dp[i][j] = dp[p][j];if (j - cost[i] >= 0) {// 可能性2 : 考虑当前主商品，只要主dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i]] + val[i]);}// fan1 : 如果有附1商品，编号给fan1，如果没有，fan1 == -1// fan2 : 如果有附2商品，编号给fan2，如果没有，fan2 == -1fan1 = fans[i] >= 1 ? follows[i][0] : -1;fan2 = fans[i] >= 2 ? follows[i][1] : -1;if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {// 可能性3 : 主 + 附1dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan1]] + val[i] + val[fan1]);}if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {// 可能性4 : 主 + 附2dp[i][j] = Math.max(dp[i][j], dp[p][j - cost[i] - cost[fan2]] + val[i] + val[fan2]);}if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {// 可能性5 : 主 + 附1 + 附2dp[i][j] = Math.max(dp[i][j],dp[p][j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);}}p = i;}}return dp[p][n];}// 空间压缩public static int compute2() {Arrays.fill(dp, 0, n + 1, 0);for (int i = 1, fan1, fan2; i <= m; i++) {if (king[i]) {for (int j = n; j >= cost[i]; j--) {dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);fan1 = fans[i] >= 1 ? follows[i][0] : -1;fan2 = fans[i] >= 2 ? follows[i][1] : -1;if (fan1 != -1 && j - cost[i] - cost[fan1] >= 0) {dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan1]] + val[i] + val[fan1]);}if (fan2 != -1 && j - cost[i] - cost[fan2] >= 0) {dp[j] = Math.max(dp[j], dp[j - cost[i] - cost[fan2]] + val[i] + val[fan2]);}if (fan1 != -1 && fan2 != -1 && j - cost[i] - cost[fan1] - cost[fan2] >= 0) {dp[j] = Math.max(dp[j],dp[j - cost[i] - cost[fan1] - cost[fan2]] + val[i] + val[fan1] + val[fan2]);}}}}return dp[n];}}

code6 非负数组前k个最小的子序列累加和

// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
// 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
// 对数器验证

01背包：
dp[i][j]：i个数，累加和为j的子序列个数

  1. dp[i-1][j]
  2. dp[i-1][j-nums[i]]
    dp[n][…]：累加和为0…n的子序列计数

堆：容量为k的优先队列
初始数据从小到大排序，放入第一个
弹出小顶堆的顶（集合），sum加入结果数组
①删除集合最后一个数，下一个放入
②再加入下一个，放入

优化：只记录当前最后一个下标

package class073;import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
// 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
// 对数器验证
public class Code06_TopKMinimumSubsequenceSum {// 暴力方法// 为了验证public static int[] topKSum1(int[] nums, int k) {ArrayList<Integer> allSubsequences = new ArrayList<>();f1(nums, 0, 0, allSubsequences);allSubsequences.sort((a, b) -> a.compareTo(b));int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = allSubsequences.get(i);}return ans;}// 暴力方法// 得到所有子序列的和public static void f1(int[] nums, int index, int sum, ArrayList<Integer> ans) {if (index == nums.length) {ans.add(sum);} else {f1(nums, index + 1, sum, ans);f1(nums, index + 1, sum + nums[index], ans);}}// 01背包来实现// 这种方法此时不是最优解// 因为n很大，数值也很大，那么可能的累加和就更大// 时间复杂度太差public static int[] topKSum2(int[] nums, int k) {int sum = 0;for (int num : nums) {sum += num;}// dp[i][j]// 1) dp[i-1][j]// 2) dp[i-1][j-nums[i]int[] dp = new int[sum + 1];dp[0] = 1;for (int num : nums) {for (int j = sum; j >= num; j--) {dp[j] += dp[j - num];}}int[] ans = new int[k];int index = 0;for (int j = 0; j <= sum && index < k; j++) {for (int i = 0; i < dp[j] && index < k; i++) {ans[index++] = j;}}return ans;}// 正式方法// 用堆来做是最优解，时间复杂度O(n * log n) + O(k * log k)public static int[] topKSum3(int[] nums, int k) {Arrays.sort(nums);// (子序列的最右下标，子序列的累加和)PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);heap.add(new int[] { 0, nums[0] });int[] ans = new int[k];for (int i = 1; i < k; i++) {int[] cur = heap.poll();int right = cur[0];int sum = cur[1];ans[i] = sum;if (right + 1 < nums.length) {heap.add(new int[] { right + 1, sum - nums[right] + nums[right + 1] });heap.add(new int[] { right + 1, sum + nums[right + 1] });}}return ans;}// 为了测试public static int[] randomArray(int len, int value) {int[] ans = new int[len];for (int i = 0; i < len; i++) {ans[i] = (int) (Math.random() * value);}return ans;}// 为了测试public static boolean equals(int[] ans1, int[] ans2) {if (ans1.length != ans2.length) {return false;}for (int i = 0; i < ans1.length; i++) {if (ans1[i] != ans2[i]) {return false;}}return true;}// 为了测试// 对数器public static void main(String[] args) {int n = 15;int v = 40;int testTime = 5000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int len = (int) (Math.random() * n) + 1;int[] nums = randomArray(len, v);int k = (int) (Math.random() * ((1 << len) - 1)) + 1;int[] ans1 = topKSum1(nums, k);int[] ans2 = topKSum2(nums, k);int[] ans3 = topKSum3(nums, k);if (!equals(ans1, ans2) || !equals(ans1, ans3)) {System.out.println("出错了！");}}System.out.println("测试结束");}}

2023-11-12 23:08:57

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/214813.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

ChatGPT 应用开发（一）ChatGPT OpenAI API 免代理调用方式（通过 Cloudflare 的 AI Gateway）

ChatGPT 应用开发（一）ChatGPT OpenAI API 免代理调用方式（通过 Cloudflare 的 AI Gateway）

前言 开发 ChatGPT 应用&#xff0c;我觉得最前置的点就是能使用 ChatGPT API 接口。首先我自己要能成功访问&#xff0c;这没问题&#xff0c;会魔法就可以本地调用。 那用户如何调用到我的应用 API 呢&#xff0c;我的理解是通过用户能访问到的中转服务器向 OpenAI 发起访问…
阅读更多...
带阻滤波器：原理、应用及性能分析？|深圳比创达电子EMC

带阻滤波器：原理、应用及性能分析？|深圳比创达电子EMC

在现代电子技术和通信领域中&#xff0c;滤波器是一种常见的电路元件&#xff0c;用于处理信号&#xff0c;去除不需要的频率成分或者增强感兴趣的频率成分。本文将重点探讨带阻滤波器&#xff0c;它是一种特殊类型的滤波器&#xff0c;具有在特定频率范围内抑制信号的功能。我…
阅读更多...
JVM Optimization Learning(五)

JVM Optimization Learning(五)

目录 一、JVM Optimization 1、G1 1、G1内存模型 2、基础概念 3、G1特点&#xff1a; 4、CMS日志分析 5、G1日志分析 2、GC参数 2.1、GC常用参数 2.2、Parallel常用参数 2.3、CMS常用参数 2.4、G1常用参数 一、JVM Optimization 1、G1 G1官网说明&#xff1a;Gar…
阅读更多...
【微软技术栈】发布自己造的轮子 -- 创建Nuget包（分布操作）

【微软技术栈】发布自己造的轮子 -- 创建Nuget包（分布操作）

目录 1、您的项目 2、创建 .nuspec 文件 3、一张图片胜过一千个拉取请求 4、包括自述文件 MD 文件 5、构建软件包 6、将包部署到 Nuget.Org 7、手动上传软件包 8、自动化和脚本化部署 9、我们如何构建和部署 ErrLog.IO Nuget 包 10、Nuget统计数据 11、最后的思考 创建 Nuget 包…
阅读更多...
生产上线需要注意的安全漏洞

生产上线需要注意的安全漏洞

一、关闭swagger 1、关闭swagger v3 # 需同时设置auto-startupfalse&#xff0c;否则/v3/api-docs等接口仍能继续访问 springfox:documentation:enabled: falseauto-startup: falseswagger-ui:enabled: false 2、关闭swagger v2 # 只要不是true就不启用 swagger:enable: fa…
阅读更多...
YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进【NO.83】将主干特征提取网络Backbone改为RevCol

YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进【NO.83】将主干特征提取网络Backbone改为RevCol

前言 作为当前先进的深度学习目标检测算法YOLOv8，已经集合了大量的trick，但是还是有提高和改进的空间，针对具体应用场景下的检测难点，可以不同的改进方法。此后的系列文章，将重点对YOLOv8的如何改进进行详细的介绍，目的是为了给那些搞科研的同学需要创新点或者搞工程项目…
阅读更多...
Vue3: 给表格多个字段添加排序功能

Vue3: 给表格多个字段添加排序功能

问题 在Vue3项目中&#xff0c;使用element-plus的表格组件绘制表格后&#xff0c;需要令表格的多个字段可以进行选择排序&#xff08;选择升序或者降序&#xff09;但是排序功能好像有时候会出错&#xff0c;需要排序的字段多了之后&#xff0c;排序功能有时候会不起作用 解…
阅读更多...
分子生成领域的stable diffusion - GEOLDM

分子生成领域的stable diffusion - GEOLDM

一、关于stable diffusion 很多人都知道stable diffusion&#xff0c;stable diffusion的出现改变了机器生成领域&#xff0c;让AI技术第一次无比的接近正常人。大语言模型&#xff0c;AIGC概念于是兴起。基于stable diffusion 大家开发了lora&#xff0c; hyperwork等微调技术…
阅读更多...
JDK 9 模块化系统 (Module System) 和 多版本兼容 Jar (Multi-Release Jar)

JDK 9 模块化系统 (Module System) 和 多版本兼容 Jar (Multi-Release Jar)

博文目录 文章目录 Module System原因JDK 模块化模块描述文件关键字 启用模块化测试结论 Multi-Release jar (MRJAR)原因原理结论用 IDEA 创建多版本兼容 Jar项目结构pom.xml测试 Module System 原因 Java 9引入了模块化系统的主要原因是为了解决Java平台面临的复杂性和可维…
阅读更多...
从电商API接口谈电商ERP系统介绍

从电商API接口谈电商ERP系统介绍

部分网友反馈小红书APP出现闪退问题。对此&#xff0c;小红书客服微博发文称&#xff0c;如遇到小红书APP无法启动的情况&#xff0c;用户可前往App Store下载最新版本&#xff08;详情可见&#xff1a; &#xff09;小红书闪退崩溃出bug&#xff0c;IT人员要背故障吗&#xff…
阅读更多...
【计算机网络实验】实验三 IP网络规划与路由设计（头歌）

【计算机网络实验】实验三 IP网络规划与路由设计（头歌）

目录 一、知识点 二、实验任务 三、头歌测试 一、知识点 IP子网掩码的两种表示方法 32位IP子网掩码&#xff0c;特点是从高位开始连续都是1&#xff0c;后面是连续的0&#xff0c;它有以下两种表示方法&#xff1a; 传统表示法&#xff0c;如&#xff1a;255.255.255.0IP前…
阅读更多...
windows下oracle透明网关安装

windows下oracle透明网关安装

上一次说了如何在Linux下安装oracle到sqlserver之间的透明网关&#xff0c;现在给大家继续介绍如何在windows下安装。 本文实验环境&#xff1a; 数据库类型 数据库版本 IP oracle 11204 192.168.238.122 MSSQL MSSQL 2008 192.168.239.40 一、oracle服务器配置ODBC源…
阅读更多...
linux软件管理

linux软件管理

八、软件管理 RPM相关命令 8.1 RPM包管理 8.1.1 RPM概述 RPM Package Manager (原Red Hat Package Manager&#xff0c;现在是一个递归缩写&#xff09; ​ 由Red Hat公司提出&#xff0c;被众多 Linux 发行版所采用也称二进制( binary code) 无需编译,可以直接使用 ​ 无法设…
阅读更多...
重磅！2023中国高校计算机大赛-人工智能创意赛结果出炉

重磅！2023中国高校计算机大赛-人工智能创意赛结果出炉

目录 中国计算机大赛-人工智能创意赛现场C4-AI大赛颁奖及留影800个AI应用&#xff1f;这届大学生真能“搞事情”AI原生时代&#xff0c;百度要再培养500大模型人才 中国计算机大赛-人工智能创意赛现场 12月8日&#xff0c;杭州&#xff0c;一位“白发老人”突然摔倒在地&#…
阅读更多...
Verilog学习 | 用initial语句写出固定的波形

Verilog学习 | 用initial语句写出固定的波形

initial beginia 0;ib 1;clk 0;#10ia 1; #20ib 0;#20ia 0; endalways #5 clk ~clk; 或者 initial clk 0;initial beginia 0;#10ia 1; #40ia 0; endinitial beginib 1;#30 ib 0; endalways #5 clk ~clk;
阅读更多...
深入探索C语言中的二叉树：数据结构之旅

深入探索C语言中的二叉树：数据结构之旅

引言 在计算机科学领域&#xff0c;数据结构是基础中的基础。在众多数据结构中&#xff0c;二叉树因其在各种操作中的高效性而脱颖而出。二叉树是一种特殊的树形结构&#xff0c;每个节点最多有两个子节点&#xff1a;左子节点和右子节点。这种结构使得搜索、插入、删除等操作…
阅读更多...
強強联手!M88明陞宣布与G2 电子竞技俱乐部成为官方合作伙伴!

強強联手!M88明陞宣布与G2 电子竞技俱乐部成为官方合作伙伴!

M88明陞作为亚洲领先的在线游戏平台&#xff0c;正式宣布与G2电子竞技俱乐部建立具有突破性意义的官方合作伙伴关系&#xff0c;G2电子竞技俱乐部是全球领先的电子竞技品牌之一。作为官方合作伙伴关系&#xff0c;双方将合作开展一系列活动。 M88明陞将在G2 电子竞技俱乐部追求…
阅读更多...
推荐4个优秀的 Python 时间序列分析库

推荐4个优秀的 Python 时间序列分析库

时间序列分析在金融和医疗保健等领域至关重要&#xff0c;在这些领域&#xff0c;理解随时间变化的数据模式至关重要。在本文中&#xff0c;我们将介绍四个主要的Python库——statmodels、tslearn、tssearch和tsfresh——每个库都针对时间序列分析的不同方面进行了定制。这些库…
阅读更多...
【cocotb】useful tools - pyfda and cocotb : filter

【cocotb】useful tools - pyfda and cocotb : filter

pyfda filter hdl generator
阅读更多...
初识人工智能，一文读懂贝叶斯优化的知识文集(6)

初识人工智能，一文读懂贝叶斯优化的知识文集(6)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023