高德地图能显示台湾省_pinterest设计网_国际军事新闻最新消息视频_优化关键词排名提升

01背包

模板

https://www.luogu.com.cn/problem/P1048

在之前的一篇 01 背包和 完全背包 的一篇解析中, 已经详细的解释了 01 背包如何想出来, 以及依赖关系是什么样的, 所以这里就直接附上代码, 只作为练习

import java.io.*;
import java.util.StringTokenizer;public class 采药 {public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main1(String[] args) throws IOException {int m = in.nextInt();int n = in.nextInt();// 前 i 个草药中 j 分钟的最大价值int[][] dp = new int[n + 1][m + 1];for (int i = 1,a,b; i <= n; i++) {a = in.nextInt();b = in.nextInt();for (int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j];if (j >= a) {dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - a] + b);}}}out.println(dp[n][m]);out.close();}public static void main(String[] args) throws IOException {int m = in.nextInt();int n = in.nextInt();// 前 i 个草药中 j 分钟的最大价值int[] dp = new int[m + 1];for (int i = 1,a,b; i <= n; i++) {a = in.nextInt();b = in.nextInt();for (int j = m; j >= a; j--) {dp[j] = dp[j];dp[j] = Math.max(dp[j],dp[j - a] + b);}}out.println(dp[m]);out.close();}public static class Read {StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}int nextInt() throws IOException {return Integer.parseInt(next());}}
}

以上的 main1 表示非空间优化的版本, main 表示进行空间优化的版本

需要一些灵感转化的 01 背包

https://leetcode.cn/problems/tJau2o

题目解析

此题最重要的是要理解, 题目中很关键的一句话, 满足获得的总优惠金额不低于超过预算的总金额
这一句话的意思我们拿题目中的数据来举例子

第一个商品原价是 100 元, 现价是 73 元, 优惠了 27 元, 我们买它要花 73 元, 我们的预算是 100 块钱, 此时买第一个商品我们还剩 100 + 27 - 73 的预算, 获得的优惠可以增加我们的预算, 也就是题目中说的冲动消费, 我们转化成 01 背包的问题

1. 设原价 a, 现价 b, 如果优惠价格 (a - b) >= b , 我们就存起来他的快乐值, 并将预算增加
2. 如果优惠价格没有达到上述的, 我们就将他存起来, 存到一个数组中, 此时问题就转化成, 我们新数组的元素, 挑前几个能满足最大预算

代码如下

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;public class bytedance_夏季特惠 {public static int MAXN = 501;public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int[][] arr = new int[MAXN][2];public static int cnt;public static void main(String[] args) throws IOException {int n = in.nextInt();int sum = in.nextInt();long ret = 0;cnt = 1;for (int i = 0,a,b,c; i < n; i++) {a = in.nextInt();b = in.nextInt();c = in.nextInt();// 可以提高预算的话, 快乐值存到 ret , 提高预算 sumif (a - 2 * b >= 0) {ret += c;sum += a - 2 * b;} else {// 否则用数组存起来arr[cnt][0] = 2 * b - a;arr[cnt++][1] = c;}}// 纯 01 背包的问题, 记住要用 long 数组, 不然会溢出long[][] dp = new long[cnt + 1][sum + 1];for (int i = 1; i <= cnt; i++) {for (int j = 0; j <= sum; j++) {dp[i][j] = dp[i - 1][j];if (j - arr[i][0] >= 0) {dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - arr[i][0]] + arr[i][1]);}}}System.out.println(ret + dp[cnt][sum]);}public static class Read {StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}int nextInt() throws IOException {return Integer.parseInt(next());}}
}

空间压缩版本

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;class Main {public static int MAXN = 501;public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int[][] arr = new int[MAXN][2];public static int cnt;public static void main(String[] args) throws IOException {int n = in.nextInt();int sum = in.nextInt();long ret = 0;cnt = 1;for (int i = 0,a,b,c; i < n; i++) {a = in.nextInt();b = in.nextInt();c = in.nextInt();if (a - 2 * b >= 0) {ret += c;sum += a - 2 * b;} else {arr[cnt][0] = 2 * b - a;arr[cnt++][1] = c;}}long[] dp = new long[sum + 1];for (int i = 1; i <= cnt; i++) {for (int j = sum; j >= arr[i][0]; j--) {dp[j] = Math.max(dp[j],dp[j - arr[i][0]] + arr[i][1]);}}out.println(ret + dp[sum]);out.close();}public static class Read {StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}int nextInt() throws IOException {return Integer.parseInt(next());}}
}

目标和(重要)

https://leetcode.cn/problems/target-sum/description/

题目解析

此题我们先从递归入手把, 也就是选和不选的关系, 但是估计大概率会超时我们先进行尝试

递归

class Solution {public int findTargetSumWays(int[] nums, int target) {return dfs(nums,target,0,0);}private int dfs(int[] nums, int target, int pos, int sum) {if (pos == nums.length) {return sum == target ? 1 : 0;}// 减int ans = 0;ans = dfs(nums,target,pos + 1,sum - nums[pos]);// 加ans += dfs(nums,target,pos + 1,sum + nums[pos]);return ans;}
}

数据量太小了, 直接跑过了, 我们来进行记忆化搜索优化一下
此题特殊的地方, 就是会出现负数, 我们需要将数组整体平移一下, 再做记忆化搜索

记忆化搜索(平移数组)

直接见代码

class Solution {public static int sum;public int findTargetSumWays(int[] nums, int target) {sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}int[][] dp = new int[nums.length][sum * 2 + 1];for (int i = 0; i < nums.length; i++) {for (int j = 0; j < sum * 2 + 1; j++) {dp[i][j] = -1;}}return dfs1(nums,target,0,0,dp);}private int dfs1(int[] nums, int target, int pos, int t, int[][] dp) {if (pos == nums.length) {return t == target ? 1 : 0;}if (dp[pos][sum + t] != -1) {return dp[pos][sum + t];}// 减int ans = 0;ans = dfs1(nums,target,pos + 1,t - nums[pos],dp);// 加ans += dfs1(nums,target,pos + 1,t + nums[pos],dp);dp[pos][sum + t] = ans;return ans;}
}

记忆化搜索(哈希表映射)

用一个哈希表套哈希表的结构, 前一个代表 i, 后一个代表 j, 查出来的值就是值

class Solution {public int findTargetSumWays(int[] nums, int target) {Map<Integer, Map<Integer,Integer>> dp = new HashMap<>();return dfs2(nums,target,0,0,dp);}private int dfs2(int[] nums, int target, int pos, int sum, Map<Integer, Map<Integer, Integer>> dp) {if (pos == nums.length) {return sum == target ? 1 : 0;}if (dp.containsKey(pos) && dp.get(pos).containsKey(sum)) {return dp.get(pos).get(sum);}// 减int ans = 0;ans = dfs2(nums,target,pos + 1,sum - nums[pos],dp);// 加ans += dfs2(nums,target,pos + 1,sum + nums[pos],dp);if (!dp.containsKey(pos)) {dp.put(pos,new HashMap<>());}dp.get(pos).put(sum,ans);return ans;}
}

要注意哈希表的判空, 防止空指针异常

01 背包

需要使用数学的公式进行转换操作, 此时 我们可以得到 arr[+] 的具体值, 我们只需要考虑从前 i 个数里 j 的容量最多能装多少种方法
直接空间优化了

public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}if ((sum + target) % 2 != 0) {return 0;}int m = (sum + target) / 2;int[] dp = new int[m + 1];dp[0] = 1;for (int num : nums) {for (int j = m; j >= 0; j--) {dp[j] = Math.max(dp[j],dp[j - num] + 1);}}return dp[m];
}

直接击败 100 % 了

最后一块石头的重量 II

https://leetcode.cn/problems/last-stone-weight-ii/description/

题目解析

这道题最难的地方是转化
此题最重要的是进行转化成 01 背包问题, 通过转化, 可以想象成两大堆的石头进行碰撞, 得出最小值
我们先求出总的值 sum, 然后进行找出最大的一半, 将 sum / 2 找出最接近这个数值的是否存在, 如果存在将 sum的大小减去 这个最大的一半的大小
(注意此处 sum / 2是否余 1, 是没有影响的, 可以举例子比如 31, 我们求出最大值 15, 另一堆一定是 16, 所以不会有影响

01 背包 (跳过二维表直接压缩)

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;// 算出 sumfor(int stone : stones) {sum += stone;}// 直接进行空间压缩的背包int m = sum / 2;boolean[] dp = new boolean[m + 1];// 0 个石头可以满足大小为 0, 初始化成 truedp[0] = true;// 正常 01 背包直接套模板了for(int stone : stones) {for(int j = m;j >= stone;j--) {dp[j] = dp[j] || dp[j - stone];}}// 遍历一下最大值是多少, 找到了直接 sum - j 是其中一堆的最大值, 减去另一堆for(int j = m;j >= 0;j--) {if(dp[j]) {return sum - j - j;}}return -1;}
}

有依赖的背包

金明的预算方案 || 购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
https://www.luogu.com.cn/problem/P1064

题目解析

两道题目是一样的, 主要是主件选了才能选择附件, 我们需要进行处理通过单独列出主件, 根据以下图解

先规定一下存储的规则, 方便进行管理, 然后梳理情况一共分成五种情况

1. 选到 i 位置的时候, 这个主件不要
2. 选到 i 位置的时候, 这个主件要
3. 选到 i 位置的时候, 这个主件要, 如果有一个附件就带上附件
4. 选到 i 位置的时候, 这个主件要, 如果有两个附件选择另外一个附件
5. 选到 i 位置的时候, 这个主件要, 如果有两个附件就带上两个附件
   直接根据以上的五种情况都选择上, 但是此题不一样的地方是我们需要标记一下每个主件的位置, 依赖上一个位置的时候我们依赖的是上一个主件的位置, 而不是 i - 1 位置

import java.io.*;
import java.util.StringTokenizer;public class Main {public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int MAXN = 32001;public static int MAXM = 61;public static boolean[] kings = new boolean[MAXM]; // 判断是否是主键public static int[] cost = new int[MAXM]; // 价钱public static int[] val = new int[MAXM]; // 重要性public static int[] fans = new int[MAXM]; // 每个主件是否存在附件, 存储有几个public static int[][] follows = new int[MAXM][2]; // 存储主键的两个附件的号数public static void main(String[] args) throws IOException {int n = in.nextInt();int m = in.nextInt();for (int i = 1; i <= m; i++) {int v = in.nextInt();int p = in.nextInt();int q = in.nextInt();cost[i] = v;val[i] = v * p;kings[i] = q == 0;if (q != 0) {follows[q][fans[q]++] = i;}}// 标记上一个主件是几号int p = 0;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {// 是主件if (kings[i]) {for (int j = 0; j <= n; j++) {// 不买主件dp[i][j] = dp[p][j];// 买一个主件if (j - cost[i] >= 0) {dp[i][j] = Math.max(dp[p][j - cost[i]] + val[i],dp[i][j]);}// 买一个主件 ＋ 第一个附件if (fans[i] >= 1 && j - cost[i] - cost[follows[i][0]] >= 0) {dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][0]]] + val[i] + val[follows[i][0]],dp[i][j]);}// 买一个主件 + 两个附件if (fans[i] >= 2 && j - cost[i] - cost[follows[i][0]] - cost[follows[i][1]] >= 0) {dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][0]] - cost[follows[i][1]]] + val[i] + val[follows[i][0]] + val[follows[i][1]],dp[i][j]);}// 买一个主件 + 第二个附件if (fans[i] >= 2 && j - cost[i] - cost[follows[i][1]] >= 0) {dp[i][j] = Math.max(dp[p][j - cost[i] - cost[follows[i][1]]] + val[i] + val[follows[i][1]],dp[i][j]);}}p = i;}}System.out.println(dp[p][n]);}public static class Read {StringTokenizer st = new StringTokenizer("");BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}int nextInt() throws IOException {return Integer.parseInt(next());}}
}

子序列累加和

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

题目解析

这题采用三种解法

1. 暴力递归, 当然可以挂上缓存, 但是空间可能会爆炸
2. 01 背包的解法, 空间还是会发生爆炸的可能, 即便空间进行压缩, 遍历也是非常大的
3. 用一个堆来进行维护每次的最小值

暴力递归

public static int[] topKSum1(int[] nums, int k) {// 存储所有的和List<Integer> ans = new ArrayList<>();ans.add(0);ans.sort((a,b) -> a - b);dfs(nums,0,0,ans);int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = ans.get(i);}return ret;
}private static void dfs(int[] nums, int pos, int sum, List<Integer> ans) {if (pos == nums.length) {ans.add(sum);return;} else {// 不选dfs(nums,pos + 1,sum,ans);// 选dfs(nums,pos + 1,sum + nums[pos],ans);}
}

01 背包(压缩过后)

public static int[] topKSum2(int[] nums, int k) {// 01 背包int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}boolean[] dp = new boolean[sum + 1];dp[0] = true;for (int i = 0; i < nums.length; i++) {for (int j = sum; j >= nums[i]; j--) {dp[j] = dp[j] || dp[j - nums[i]];}}int[] ans = new int[k];int cnt = 0;for (int i = 0; i <= sum; i++) {if (dp[i] && cnt < k){ans[cnt++] = i;}}return ans;
}

还是可能空间爆炸

堆 + 贪心