class074 背包dp-分组背包、完全背包【算法】

package class074;
// 分组背包(模版)
// 给定一个正数m表示背包的容量，有n个货物可供挑选
// 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)
// 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
// 怎么挑选货物能达到价值最大，返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1757
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"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_PartitionedKnapsack {
  public static int MAXN = 1001;
  public static int MAXM = 1001;
  // arr[i][0] i号物品的体积
  // arr[i][1] i号物品的价值
  // arr[i][2] i号物品的组号
  public static int[][] arr = new int[MAXN][3];
  public static int[] dp = new int[MAXM];
  public static int m, 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) {
      m = (int) in.nval;
      in.nextToken();
      n = (int) in.nval;
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        arr[i][0] = (int) in.nval;
        in.nextToken();
        arr[i][1] = (int) in.nval;
        in.nextToken();
        arr[i][2] = (int) in.nval;
      }
      Arrays.sort(arr, 1, n + 1, (a, b) -> a[2] - b[2]);
      out.println(compute1());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 严格位置依赖的动态规划
  public static int compute1() {
    int teams = 1;
    for (int i = 2; i <= n; i++) {
      if (arr[i - 1][2] != arr[i][2]) {
        teams++;
      }
    }
    // 组的编号1~teams
    // dp[i][j] : 1~i是组的范围，每个组的物品挑一件，容量不超过j的情况下，最大收益
    int[][] dp = new int[teams + 1][m + 1];
    // dp[0][....] = 0
    for (int start = 1, end = 2, i = 1; start <= n; i++) {
      while (end <= n && arr[end][2] == arr[start][2]) {
        end++;
      }
      // start ... end-1 -> i组
      for (int j = 0; j <= m; j++) {
        // arr[start...end-1]是当前组，组号一样
        // 其中的每一件商品枚举一遍
        dp[i][j] = dp[i - 1][j];
        for (int k = start; k < end; k++) {
          // k是组内的一个商品编号
          if (j - arr[k][0] >= 0) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
          }
        }
      }
      // start去往下一组的第一个物品
      // 继续处理剩下的组
      start = end++;
    }
    return dp[teams][m];
  }
  // 空间压缩
  public static int compute2() {
    // dp[0][...] = 0
    Arrays.fill(dp, 0, m + 1, 0);
    for (int start = 1, end = 2; start <= n;) {
      while (end <= n && arr[end][2] == arr[start][2]) {
        end++;
      }
      // start....end-1
      for (int j = m; j >= 0; j--) {
        for (int k = start; k < end; k++) {
          if (j - arr[k][0] >= 0) {
            dp[j] = Math.max(dp[j], arr[k][1] + dp[j - arr[k][0]]);
          }
        }
      }
      start = end++;
    }
    return dp[m];
  }
}

package class074;
import java.util.List;
// 从栈中取出K个硬币的最大面值和
// 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币
// 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里
// 给你一个列表 piles ，其中 piles[i] 是一个整数数组
// 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k
// 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少
// 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
public class Code02_MaximumValueOfKcoinsFromPiles {
  // piles是一组一组的硬币
  // m是容量，表示一定要进行m次操作
  // dp[i][j] : 1~i组上，一共拿走j个硬币的情况下，获得的最大价值
  // 1) 不要i组的硬币 : dp[i-1][j]
  // 2) i组里尝试每一种方案
  // 比如，i组里拿走前k个硬币的方案 : dp[i-1][j-k] + 从顶部开始前k个硬币的价值和
  // 枚举每一个k，选出最大值
  public static int maxValueOfCoins1(List<List<Integer>> piles, int m) {
    int n = piles.size();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      // i从1组开始（我们的设定），但是题目中的piles是从下标0开始的
      // 所以来到i的时候，piles.get(i-1)是当前组
      List<Integer> team = piles.get(i - 1);
      int t = Math.min(team.size(), m);
      // 预处理前缀和，为了加速计算
      int[] preSum = new int[t + 1];
      for (int j = 0, sum = 0; j < t; j++) {
        sum += team.get(j);
        preSum[j + 1] = sum;
      }
      // 更新动态规划表
      for (int j = 0; j <= m; j++) {
        // 当前组一个硬币也不拿的方案
        dp[i][j] = dp[i - 1][j];
        for (int k = 1; k <= Math.min(t, j); k++) {
          dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k] + preSum[k]);
        }
      }
    }
    return dp[n][m];
  }
  // 空间压缩
  public static int maxValueOfCoins2(List<List<Integer>> piles, int m) {
    int[] dp = new int[m + 1];
    for (List<Integer> team : piles) {
      int t = Math.min(team.size(), m);
      int[] preSum = new int[t + 1];
      for (int j = 0, sum = 0; j < t; j++) {
        sum += team.get(j);
        preSum[j + 1] = sum;
      }
      for (int j = m; j > 0; j--) {
        for (int k = 1; k <= Math.min(t, j); k++) {
          dp[j] = Math.max(dp[j], dp[j - k] + preSum[k]);
        }
      }
    }
    return dp[m];
  }
}

package class074;
// 完全背包(模版)
// 给定一个正数t，表示背包的容量
// 有m种货物，每种货物可以选择任意个
// 每种货物都有体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1616
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"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 Code03_UnboundedKnapsack {
  public static int MAXM = 10001;
  public static int MAXT = 10000001;
  public static int[] cost = new int[MAXM];
  public static int[] val = new int[MAXM];
  public static long[] dp = new long[MAXT];
  public static int t, m;
  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();
      m = (int) in.nval;
      for (int i = 1; i <= m; i++) {
        in.nextToken();
        cost[i] = (int) in.nval;
        in.nextToken();
        val[i] = (int) in.nval;
      }
      out.println(compute2());
    }
    out.flush();
    out.close();
    br.close();
  }
  // 严格位置依赖的动态规划
  // 会空间不够，导致无法通过全部测试用例
  public static long compute1() {
    // dp[0][.....] = 0
    int[][] dp = new int[m + 1][t + 1];
    for (int i = 1; i <= m; i++) {
      for (int j = 0; j <= t; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j - cost[i] >= 0) {
          dp[i][j] = Math.max(dp[i][j], dp[i][j - cost[i]] + val[i]);
        }
      }
    }
    return dp[m][t];
  }
  // 空间压缩
  // 可以通过全部测试用例
  public static long compute2() {
    Arrays.fill(dp, 1, t + 1, 0);
    for (int i = 1; i <= m; i++) {
      for (int j = cost[i]; j <= t; j++) {
        dp[j] = Math.max(dp[j], dp[j - cost[i]] + val[i]);
      }
    }
    return dp[t];
  }
}

package class074;
// 正则表达式匹配
// 给你字符串s、字符串p
// s中一定不含有'.'、'*'字符，p中可能含有'.'、'*'字符
// '.' 表示可以变成任意字符，数量1个
// '*' 表示可以让 '*' 前面那个字符数量任意(甚至可以是0个)
// p中即便有'*'，一定不会出现以'*'开头的情况，也一定不会出现多个'*'相邻的情况(无意义)
// 请实现一个支持 '.' 和 '*' 的正则表达式匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/regular-expression-matching/
public class Code04_RegularExpressionMatching {
  public static boolean isMatch1(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    return f1(s, p, 0, 0);
  }
  // s[i....]能不能被p[j....]完全匹配出来
  // p[j]这个字符，一定不是'*'
  public static boolean f1(char[] s, char[] p, int i, int j) {
    if (i == s.length) {
      // s没了
      if (j == p.length) {
        // 如果p也没了，返回true
        return true;
      } else {
        // p还剩下一些后缀
        // 如果p[j+1]是*，那么p[j..j+1]可以消掉，然后看看p[j+2....]是不是都能消掉
        return j + 1 < p.length && p[j + 1] == '*' && f1(s, p, i, j + 2);
      }
    } else if (j == p.length) {
      // s有后缀
      // p没后缀了
      return false;
    } else {
      // s有后缀
        // p有后缀
      if (j + 1 == p.length || p[j + 1] != '*') {
        // s[i....]
        // p[j....]
        // 如果p[j+1]不是*，那么当前的字符必须能匹配：(s[i] == p[j] || p[j] == '?')
        // 同时，后续也必须匹配上：process1(s, p, i + 1, j + 1);
        return (s[i] == p[j] || p[j] == '.') && f1(s, p, i + 1, j + 1);
      } else {
        // 如果p[j+1]是*
        // 完全背包！
        // s[i....]
        // p[j....]
        // 选择1: 当前p[j..j+1]是x*，就是不让它搞定s[i]，那么继续 : process1(s, p, i, j + 2)
        boolean p1 = f1(s, p, i, j + 2);
        // 选择2: 当前p[j..j+1]是x*，如果可以搞定s[i]，那么继续 : process1(s, p, i + 1, j)
        // 如果可以搞定s[i] : (s[i] == p[j] || p[j] == '.')
        // 继续匹配 : process1(s, p, i + 1, j)
        boolean p2 = (s[i] == p[j] || p[j] == '.') && f1(s, p, i + 1, j);
        // 两个选择，有一个可以搞定就返回true，都无法搞定返回false
        return p1 || p2;
      }
    }
  }
  // 记忆化搜索
  public static boolean isMatch2(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    int n = s.length;
    int m = p.length;
    // dp[i][j] == 0，表示没算过
    // dp[i][j] == 1，表示算过，答案是true
    // dp[i][j] == 2，表示算过，答案是false
    int[][] dp = new int[n + 1][m + 1];
    return f2(s, p, 0, 0, dp);
  }
  public static boolean f2(char[] s, char[] p, int i, int j, int[][] dp) {
    if (dp[i][j] != 0) {
      return dp[i][j] == 1;
    }
    boolean ans;
    if (i == s.length) {
      if (j == p.length) {
        ans = true;
      } else {
        ans = j + 1 < p.length && p[j + 1] == '*' && f2(s, p, i, j + 2, dp);
      }
    } else if (j == p.length) {
      ans = false;
    } else {
      if (j + 1 == p.length || p[j + 1] != '*') {
        ans = (s[i] == p[j] || p[j] == '.') && f2(s, p, i + 1, j + 1, dp);
      } else {
        ans = f2(s, p, i, j + 2, dp) || ((s[i] == p[j] || p[j] == '.') && f2(s, p, i + 1, j, dp));
      }
    }
    dp[i][j] = ans ? 1 : 2;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static boolean isMatch3(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    int n = s.length;
    int m = p.length;
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[n][m] = true;
    for (int j = m - 1; j >= 0; j--) {
      dp[n][j] = j + 1 < m && p[j + 1] == '*' && dp[n][j + 2];
    }
    for (int i = n - 1; i >= 0; i--) {
      for (int j = m - 1; j >= 0; j--) {
        if (j + 1 == m || p[j + 1] != '*') {
          dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i + 1][j + 1];
        } else {
          dp[i][j] = dp[i][j + 2] || ((s[i] == p[j] || p[j] == '.') && dp[i + 1][j]);
        }
      }
    }
    return dp[0][0];
  }
}

package class074;
// 通配符匹配（和题目4高度相似，只是边界条件不同而已，而且更简单）
// 给你字符串s、字符串p
// s中一定不含有'?'、'*'字符，p中可能含有'?'、'*'字符
// '?' 表示可以变成任意字符，数量1个
// '*' 表示可以匹配任何字符串
// 请实现一个支持 '?' 和 '*' 的通配符匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/wildcard-matching/
public class Code05_WildcardMatching {
  // 暴力递归
  public static boolean isMatch1(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    return f1(s, p, 0, 0);
  }
  // s[i....]能不能被p[j....]完全匹配出来
  public static boolean f1(char[] s, char[] p, int i, int j) {
    if (i == s.length) {
      // s没了
      if (j == p.length) {
        // 如果p也没了，返回true
        return true;
      } else {
        // 如果p[j]是*，可以消掉，然后看看p[j+1....]是不是都能消掉
        return p[j] == '*' && f1(s, p, i, j + 1);
      }
    } else if (j == p.length) {
      // s有
      // p没了
      return false;
    } else {
      if (p[j] != '*') {
        // s[i....]
        // p[j....]
        // 如果p[j]不是*，那么当前的字符必须能匹配：(s[i] == p[j] || p[j] == '?')
        // 同时，后续也必须匹配上：process1(s, p, i + 1, j + 1);
        return (s[i] == p[j] || p[j] == '?') && f1(s, p, i + 1, j + 1);
      } else {
        // s[i....]
        // p[j....]
        // 如果p[j]是*
        // 选择1: 反正当前p[j]是*，必然可以搞定s[i]，那么继续 : process1(s, p, i + 1, j)
        // 选择2: 虽然当前p[j]是*，但就是不让它搞定s[i]，那么继续 : process1(s, p, i, j + 1)
        // 两种选择有一个能走通，答案就是true；如果都搞不定，答案就是false
        return f1(s, p, i + 1, j) || f1(s, p, i, j + 1);
      }
    }
  }
  // 记忆化搜索
  public static boolean isMatch2(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    int n = s.length;
    int m = p.length;
    // dp[i][j] == 0，表示没算过
    // dp[i][j] == 1，表示算过，答案是true
    // dp[i][j] == 2，表示算过，答案是false
    int[][] dp = new int[n + 1][m + 1];
    return f2(s, p, 0, 0, dp);
  }
  public static boolean f2(char[] s, char[] p, int i, int j, int[][] dp) {
    if (dp[i][j] != 0) {
      return dp[i][j] == 1;
    }
    boolean ans;
    if (i == s.length) {
      if (j == p.length) {
        ans = true;
      } else {
        ans = p[j] == '*' && f2(s, p, i, j + 1, dp);
      }
    } else if (j == p.length) {
      ans = false;
    } else {
      if (p[j] != '*') {
        ans = (s[i] == p[j] || p[j] == '?') && f2(s, p, i + 1, j + 1, dp);
      } else {
        ans = f2(s, p, i + 1, j, dp) || f2(s, p, i, j + 1, dp);
      }
    }
    dp[i][j] = ans ? 1 : 2;
    return ans;
  }
  // 严格位置依赖的动态规划
  public static boolean isMatch3(String str, String pat) {
    char[] s = str.toCharArray();
    char[] p = pat.toCharArray();
    int n = s.length;
    int m = p.length;
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[n][m] = true;
    for (int j = m - 1; j >= 0 && p[j] == '*'; j--) {
      dp[n][j] = true;
    }
    for (int i = n - 1; i >= 0; i--) {
      for (int j = m - 1; j >= 0; j--) {
        if (p[j] != '*') {
          dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i + 1][j + 1];
        } else {
          dp[i][j] = dp[i + 1][j] || dp[i][j + 1];
        }
      }
    }
    return dp[0][0];
  }
}

package class074;
// 购买足量干草的最小花费
// 有n个提供干草的公司，每个公司都有两个信息
// cost[i]代表购买1次产品需要花的钱
// val[i]代表购买1次产品所获得的干草数量
// 每个公司的产品都可以购买任意次
// 你一定要至少购买h数量的干草，返回最少要花多少钱
// 测试链接 : https://www.luogu.com.cn/problem/P2918
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"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 Code06_BuyingHayMinimumCost {
  public static int MAXN = 101;
  public static int MAXM = 55001;
  public static int[] val = new int[MAXN];
  public static int[] cost = new int[MAXN];
  public static int[] dp = new int[MAXM];
  public static int n, h, maxv, m;
  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();
      h = (int) in.nval;
      maxv = 0;
      for (int i = 1; i <= n; i++) {
        in.nextToken();
        val[i] = (int) in.nval;
        maxv = Math.max(maxv, val[i]);
        in.nextToken();
        cost[i] = (int) in.nval;
      }
      // 最核心的一句
      // 包含重要分析
      m = h + maxv;
      out.println(compute2());
    }
    out.flush();
    out.close();
    br.close();
  }
  // dp[i][j] : 1...i里挑公司，购买严格j磅干草，需要的最少花费
  // 1) dp[i-1][j]
  // 2) dp[i][j-val[i]] + cost[i]
  // 两种可能性中选最小
  // 但是关于j需要进行一定的扩充，原因视频里讲了
  public static int compute1() {
    int[][] dp = new int[n + 1][m + 1];
    Arrays.fill(dp[0], 1, m + 1, Integer.MAX_VALUE);
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j - val[i] >= 0 && dp[i][j - val[i]] != Integer.MAX_VALUE) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j - val[i]] + cost[i]);
        }
      }
    }
    int ans = Integer.MAX_VALUE;
    // >= h
    // h h+1 h+2 ... m
    for (int j = h; j <= m; j++) {
      ans = Math.min(ans, dp[n][j]);
    }
    return ans;
  }
  // 空间压缩
  public static int compute2() {
    Arrays.fill(dp, 1, m + 1, Integer.MAX_VALUE);
    for (int i = 1; i <= n; i++) {
      for (int j = val[i]; j <= m; j++) {
        if (dp[j - val[i]] != Integer.MAX_VALUE) {
          dp[j] = Math.min(dp[j], dp[j - val[i]] + cost[i]);
        }
      }
    }
    int ans = Integer.MAX_VALUE;
    for (int j = h; j <= m; j++) {
      ans = Math.min(ans, dp[j]);
    }
    return ans;
  }
}