目录
01背包模型
题目
dp
滚动数组优化
第一问
第二问
扩展
完全背包
题目
动态规划编辑
滚动数组优化
关于-1的代码层面优化
💰🪙
背包就是有限制条件的组合问题
01背包模型
题目
有一个背包能容纳的体积是v,现在有n个物品,第i个物品的体积为vi,价值为wi。
(1)求这个背包至多能装多大价值的物品?
(2) 若背包恰好装满,求至多能装多大价值的物品?
输入描述:
第一行两个整数n和V,表示物品个数和背包体积接下来n行,每行两个数;vi,wi表示第i个物品的体积和价值
1 < n,V,vi,wi < 1000
dp[i][j] 表示从前i个位置选,总体积不超过 j /等于j ,所有选择中,最大的价值。
dp
import java.util.Scanner;
public class KnapsackProblem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n, V;
// 物品个数
n = scanner.nextInt();
// 背包体积
V = scanner.nextInt();
int[] vi = new int[n];
int[] wi = new int[n];
for (int i = 0; i < n; i++) {
// 第 i 个物品的体积
vi[i] = scanner.nextInt();
// 第 i 个物品的价值
wi[i] = scanner.nextInt();
}
int maxValue1 = maxValue(vi, wi, V);
int maxValue2 = maxValueFilled(vi, wi, V);
System.out.println("问题 1:背包至多能装价值为 " + maxValue1 + " 的物品");
System.out.println("问题 2:背包恰好装满时,能装价值为 " + maxValue2 + " 的物品");
}
public static int maxValue(int[] vi, int[] wi, int V) {
int n = vi.length;
int[][] dp = new int[n + 1][V + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (vi[i - 1] <= j) {
// 选择放入当前物品和不放入当前物品之间的较大值
dp[i][j] = Math.max(dp[i - 1][j], wi[i - 1] + dp[i - 1][j - vi[i - 1]]);
} else {
// 如果当前物品的体积大于背包的剩余容量,则无法放入当前物品,继承之前的最优解
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][V];
}
public static int maxValueFilled(int[] vi, int[] wi, int V) {
int n = vi.length;
int[][] dp = new int[n + 1][V + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (vi[i - 1] <= j) {
// 选择放入当前物品和不放入当前物品之间的较大值
dp[i][j] = Math.max(dp[i - 1][j], wi[i - 1] + dp[i - 1][j - vi[i - 1]]);
} else {
// 如果当前物品的体积大于背包的剩余容量,则无法放入当前物品,继承之前的最优解
dp[i][j] = dp[i - 1][j];
}
}
}
// 检查最后一行是否存在等于背包容量的最优解
for (int j = V; j >= 0; j--) {
if (dp[n][j] == dp[n][j]) {
return dp[n][j];
}
}
return 0;
}
}
滚动数组优化
普通的就用两个数组,1推2,1做3;
这里使用一个数组,从右往左计算覆盖。修改j的遍历顺序,去掉所有i
第一问
//✅滚动数组
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v=in.nextInt();
int n=in.nextInt();
int[] vi=new int[n+1];
int[] wi=new int[n+1];
for(int i=1;i<=n;i++){
vi[i]=in.nextInt();
wi[i]=in.nextInt();
}
int[] dp=new int[v+1];
for(int i=1;i<=n;i++){
for(int j=v;j>=vi[i];j--){//从右往左
dp[j]=Math.max(dp[j],wi[i]+dp[j-vi[i]]);
}
}
System.out.println(dp[v]);
}
}
//✅原本
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int v=in.nextInt();
int n=in.nextInt();
int[] vi=new int[n+1];
int[] wi=new int[n+1];
for(int i=1;i<=n;i++){
vi[i]=in.nextInt();
wi[i]=in.nextInt();
}
int[][] dp=new int[n+1][v+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=v;j++){
dp[i][j]=dp[i-1][j];
if(j>=vi[i]) dp[i][j]=Math.max(dp[i-1][j],wi[i]+dp[i-1][j-vi[i]]);
}//这里dp[i][j]=Math.max(dp[i][j]也可以
}
System.out.println(dp[n][v]);
}
}
第二问
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int V = in.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
int[] dp = new int[V + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = V; j >= v[i]; j--) {
if (dp[j - v[i]] != -1) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
System.out.println(dp[V] == -1 ? -1 : dp[V]);
}
}
//💡原本
for (int j = 1; j <= V; j++) {
dp[0][j] = -1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i - 1][j - v[i]] != -1) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
return dp[n][V]==-1?0:dp[n][V];
扩展
比如目标和,可以思考为一个位置的选与不选。
nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
就可以把数组分成两部分,一部分是a(所有+的和),b(所有-的和的绝对值)假设a>b,有a+b=sum,a-b=target;解出a=(sum+target)/2,即找价值是a....。
//🤑求凑成目标和的方法个数 总的状态方程dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]; dp[0][0]=1
还有一道题按照abcde计算最后结果就是+a-b+d+c-e随便写的,就是在abcde前面加上正号或者负号,想起来 上面的题;那就是把数组分成俩部分,一边是a,一边是b,其中sum=a+b,这道题想让a-b值最小,那就a,b差不多一样大的时候,寻找a=sum/2的背包 。
二维背包问题
dp[i][j][k]表示从前i个字符中选,0的个数不超过m,1的个数不超过n,所有选法中,字符子集的个数。
给你一个二进制字符串数组
strs
和两个整数m
和n
。请你找出并返回
strs
的最大子集的长度,该子集中 最多 有m
个0
和n
个1
。如果
x
的所有元素也是y
的元素,集合x
是集合y
的 子集 。示例 1:文章来源地址https://www.toymoban.com/news/detail-806668.html
输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出:4 解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。class Solution { public int findMaxForm(String[] strs, int m, int n) { int len=strs.length; int[][][] dp=new int[len+1][m+1][n+1]; for(int i=1;i<len+1;i++){ int a=0,b=0; for(char ch:strs[i-1].toCharArray()){ if(ch=='0')a++; else b++; } for(int j=0;j<=m;j++){ for(int k=0;k<=n;k++){ dp[i][j][k]=dp[i-1][j][k]; if(j>=a&&k>=b){ dp[i][j][k]=Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1); } } } } return dp[len][m][n]; } }
如果给另一个题盈利plan,dp[i][j][k]表示从前i个计划中选,总人数不超过j,总利润至少是k,一共有多少种选法?dp[0][j][0]=1,了解到空集也是一种选法。
dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-g[i][Math.max(0,k-p[i]),其中满足j>=g[i]成立
完全背包
题目
描述、
你有一个背包,最多能容纳的体积是V。
现在有n种物品每种物品有任意多个第i种物品的体积为vi,价值为wi。
示例
求这个背包至多能装多大价值的物品?
(2) 若背包恰好装满,求至多能装多大价值的物品?
输入描述:
第一行两个整数n和V,表示物品个数和背包体积接下来n行,每行两个数u;和wi,表示第种物品的体积和价值.1 n,V < 1000
说
输出描述:
输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。
动态规划
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int V = scanner.nextInt(); int[] v = new int[n + 1]; int[] w = new int[n + 1]; for (int i = 1; i <= n; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } int[][] dp = new int[n + 1][V + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= V; j++) { dp[i][j] = dp[i - 1][j]; if (j >= v[i]) { dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]); } } } System.out.println(dp[n][V]); int[][] dp2 = new int[n + 1][V + 1]; for (int j = 1; j <= V; j++) { dp2[0][j] = -1; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= V; j++) { dp2[i][j] = dp2[i - 1][j]; if (j >= v[i] && dp2[i][j - v[i]] != -1) { dp2[i][j] = Math.max(dp2[i][j], dp2[i][j - v[i]] + w[i]); } } } int ret = dp2[n][V] == -1 ? 0 : dp2[n][V]; System.out.println(ret); } }
滚动数组优化
根据dp[i][j]位置的依赖关系判断,j从左往右遍历
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int V = scanner.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= V; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[V]);
int[] dp2 = new int[V + 1];
for (int j = 1; j <= V; j++) {
dp2[j] = -1;
}
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= V; j++) {
if (dp2[j - v[i]] != -1) {
dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
}
}
}
int ret = dp2[V] == -1 ? 0 : dp2[V];
System.out.println(ret);
}
}
关于-1的代码层面优化
int[] dp2 = new int[V + 1]; for (int j = 1; j <= V; j++) { dp2[j] = -0x3f3f3f3f; } for (int i = 1; i <= n; i++) { for (int j = v[i]; j <= V; j++) { dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]); } } int ret = dp2[V]<0 ? 0 : dp2[V]; System.out.println(ret);
💰🪙
求凑成amount的最少的硬币个数
给你一个整数数组
coins
,表示不同面额的硬币;以及一个整数amount
,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回
-1
。你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins =[1, 2, 5]
, amount =11
输出:3
解释:11 = 5 + 5 + 1class Solution { public int coinChange(int[] coins, int amount) { int n=coins.length;int INF=0x3f3f3f3f; //不用Integer.MAX_VALUE因为这个+1——》变小,越界 int[][] dp=new int[n+1][amount+1]; for(int j=1;j<=amount;j++) dp[0][j]=INF; for(int i=1;i<=n;i++){ for(int j=0;j<=amount;j++){ dp[i][j]=dp[i-1][j]; if(j-coins[i-1]>=0){ dp[i][j]=Math.min(dp[i][j],dp[i][j-coins[i-1]]+1); } } } return dp[n][amount]>=INF?-1:dp[n][amount];//别忘了 } }
class Solution { public int coinChange(int[] coins, int amount) { int n=coins.length;int INF=0x3f3f3f3f; //💡不用Integer.MAX_VALUE因为这个+1——》变小,越界 int[] dp=new int[amount+1]; for(int j=1;j<=amount;j++) dp[j]=INF; for(int i=1;i<=n;i++){ for(int j=coins[i-1];j<=amount;j++){ dp[j]=Math.min(dp[j],dp[j-coins[i-1]]+1); } } return dp[amount]>=INF?-1:dp[amount];//别忘了 } }
凑成面值amount的硬币组合数
给你一个整数数组
coins
表示不同面额的硬币,另给一个整数amount
表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回
0
。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。文章来源:https://www.toymoban.com/news/detail-806668.html
示例 1:
输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1class Solution { public int change(int amount, int[] coins) { int n=coins.length; int[][] dp=new int[n+1][amount+1]; dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=amount;j++){ dp[i][j]=dp[i-1][j]; if(j-coins[i-1]>=0) dp[i][j]+=dp[i][j-coins[i-1]]; } } return dp[n][amount]; } }
到了这里,关于动态规划——01背包和完全背包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!