建站哪个平台好,四川建设网官网入口,网站建设尢金手指专业,网站开发承诺函经典版
题目链接#xff1a;1.小明的背包1 - 蓝桥云课 (lanqiao.cn) 01背包问题中#xff0c;每种物品只有两种状态#xff0c;即拿或不拿。设状态dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v)#xff1b;如果不拿物品i#xff0c;那么最大价值就是dp[i-1][j]#xff0c;如果…经典版
题目链接1.小明的背包1 - 蓝桥云课 (lanqiao.cn) 01背包问题中每种物品只有两种状态即拿或不拿。设状态dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v)如果不拿物品i那么最大价值就是dp[i-1][j]如果拿了就是从体积j-v转移过来体积会变大w价值增加v最后输出dp[N][V]。 package lanqiao;import java.util.Scanner;/*** 2024/3/13* 背包容量为V商场一共有N件物品第i件物品的体积为wi价值为vi* 求不超过体积的情况下所获得的最大价值为多少*/
public class lanqiao1174_小明的背包1 {public static void main(String[] args) {Scanner scannew Scanner(System.in);int Nscan.nextInt();//物品个数int Vscan.nextInt();//背包容量int[] wnew int[N];//物品体积int[] vnew int[N];//物品价值for (int i0;iN;i){//输入体积和价值w[i]scan.nextInt();v[i]scan.nextInt();}int[][] dpnew int[N1][V1];for (int i1;iN;i){for (int j1;jV;j){dp[i][j]dp[i-1][j];if (jw[i-1]) {dp[i][j] Math.max(dp[i][j], dp[i - 1][j - w[i - 1]] v[i - 1]);}}}System.out.println(最大价值为dp[N][V]);}
}5 20
1 6
2 5
3 8
5 15
3 3
最大价值为37进程已结束退出代码为 0
升阶版 01背包的优化 首先有dp[i][j]dp[i-1][j]相当于将dp[i-1]复制给dp[i]然后dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v)每次下标都是从小转移到大由此可以将第一维度优化掉直接设置一个一维数组每次更新都从后往前更新即变为dp[j]max(dp[j],dp[j-w]v)dp[j]表示此时物品总重量为j的情况下的最大价值 题目链接1.背包与魔法 - 蓝桥云课 (lanqiao.cn) 设状态dp[i][j]表示物品总重量为i且使用了j次魔法的情况下的最大值。 对于每个物品有三种选择不选、选但不使用魔法、选且使用魔法 dp[j][0] Math.max(dp[j][0], dp[j - w][0] v); dp[j][1] Math.max(dp[j - w - K][0] v * 2, dp[j][1]); 其中dp[j][1]dp[j][0] 最后输出 Math.max(dp[M][0], dp[M][1]) package lanqiao;import java.util.Scanner;/*** 2024/3/13* 小蓝有N件物品其中第i件重量是Wi价值是Vi。他有一个背包最大承重是M* 求最多能装总价值多少的wupin* 其中小蓝可以使用一个魔法仅一次将一件物品的重量增加K同时价值翻倍当然也可以不使用魔法*/
public class lanqiao2223_背包与魔法 {public static void main(String[] args) {Scanner scan new Scanner(System.in);int N scan.nextInt();//物品数量int M scan.nextInt();//背包体积int K scan.nextInt();//魔法增重int[] w new int[N];int[] v new int[N];for (int i 0; i N; i) {w[i] scan.nextInt();v[i] scan.nextInt();}int[][] dp new int[M 1][2];//定义一个二维数组一个表示未用魔法的一个表示使用魔法的dp[ ][0] dp[ ][1]for (int i 1; i N; i) {for (int j M; j 0; j--) {if (j w[i - 1]) {dp[j][0] Math.max(dp[j][0], dp[j - w[i - 1]][0] v[i - 1]);//未使用魔法的情况dp[j][1] Math.max(dp[j][1], dp[j - w[i - 1]][1] v[i - 1]);//通过将为使用魔法的数值复制存储方便进行下面使用魔法情况的运算}if (j w[i - 1] K) {//考虑使用魔法情况上述将同一个结果分别存储在不同维度也是为了此处计算不影响结果dp[j][1] Math.max(dp[j - w[i - 1] - K][0] v[i - 1] * 2, dp[j][1]);}}}System.out.println(最大价值为 Math.max(dp[M][0], dp[M][1]));//比较使用魔法和未使用魔法的情况输出较大的结果}
}3 10 3
5 10
4 9
3 8
最大价值为26进程已结束退出代码为 0
