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

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];
  }
}

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];
  }
}

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 + 1
    int 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];
  }
}

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];
  }
}

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 == -1
          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) {
            // 可能性3 : 主 + 附1
            dp[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 : 主 + 附2
            dp[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 + 附2
            dp[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];
  }
}

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("测试结束");
  }
}