class074 背包dp-分组背包、完全背包【算法】
算法讲解074【必备】背包dp-分组背包、完全背包
code1 P1757 通天之分组背包
// 分组背包(模版)
// 给定一个正数m表示背包的容量，有n个货物可供挑选
// 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)
// 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量
// 怎么挑选货物能达到价值最大，返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1757
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
分组背包
dp[i][j]：1…i组容量为j的最大价值
dp[i-1][j]
dp[i][j-k]+k，k是组内选择
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];
}
}
code2 2218. 从栈中取出 K 个硬币的最大面值和
// 从栈中取出K个硬币的最大面值和
// 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币
// 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里
// 给你一个列表 piles ，其中 piles[i] 是一个整数数组
// 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k
// 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少
// 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
把选择的方案看成组数，方案为选几个硬币的前缀和
dp[i][j]：1…i组容量为j选择的最大面额
dp[i-1][j]
dp[i-1][j-k]+k，k表示组内选择
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];
}
}
code3 P1616 疯狂的采药
// 完全背包(模版)
// 给定一个正数t，表示背包的容量
// 有m种货物，每种货物可以选择任意个
// 每种货物都有体积costs[i]和价值values[i]
// 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大
// 返回最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1616
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
完全背包：
dp[i][j]：1…i容量为j的最大价值
dp[i-1][j]
dp[i][j-costs[i]]+values[i]，j-costs[i]>=0
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];
}
}
code4 10. 正则表达式匹配
// 正则表达式匹配
// 给你字符串s、字符串p
// s中一定不含有’.‘、’‘字符，p中可能含有’.‘、’‘字符
// ‘.’ 表示可以变成任意字符，数量1个
// ‘’ 表示可以让 '’ 前面那个字符数量任意(甚至可以是0个)
// p中即便有’‘，一定不会出现以’‘开头的情况，也一定不会出现多个’'相邻的情况(无意义)
// 请实现一个支持 ‘.’ 和 '’ 的正则表达式匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/regular-expression-matching/
f(s,p,i,j)：s[i…]能不能被p[j…]完全匹配出来
i,j都到末尾了，匹配成功
一个没到匹配失败
p[j+1]!=‘*’
(s[i]==p[j]||p[j]=='.')&&f(s,p,i+1,j+1)
p[j+1]=='*'时
f(s,p,i,j+2)，s不匹配x*
f(s,p,i+1,j)，s匹配x*
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];
}
}
code5 44. 通配符匹配
// 通配符匹配（和题目4高度相似，只是边界条件不同而已，而且更简单）
// 给你字符串s、字符串p
// s中一定不含有’?‘、’‘字符，p中可能含有’?‘、’'字符
// ‘?’ 表示可以变成任意字符，数量1个
// ‘’ 表示可以匹配任何字符串
// 请实现一个支持 ‘?’ 和 '’ 的通配符匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/wildcard-matching/
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];
}
}
code6 P2918 [USACO08NOV] Buying Hay S
// 购买足量干草的最小花费
// 有n个提供干草的公司，每个公司都有两个信息
// cost[i]代表购买1次产品需要花的钱
// val[i]代表购买1次产品所获得的干草数量
// 每个公司的产品都可以购买任意次
// 你一定要至少购买h数量的干草，返回最少要花多少钱
// 测试链接 : https://www.luogu.com.cn/problem/P2918
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
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;
}
}
2023-11-15 20:34:24
