解题思路:
dp[i][j]表示面对第 i 个物品时,最大重量 j 的背包所拥有的最大价值
打表,找出状态转移方程:
if(j<w[i]){ //不拿
dp[i][j]=dp[i-1][j];
}else{ //拿或不拿
dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
}
参考代码:
方法一:二维dp表
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m=sc.nextInt(); //物品个数、背包最大重量 int[] w=new int[n+1]; int[] v=new int[n+1]; int[][] dp=new int[n+1][m+1]; for(int i=1;i<n+1;i++){ w[i]=sc.nextInt(); v[i]=sc.nextInt(); } for(int i=1;i<n+1;i++){ //第i个物品 for(int j=1;j<m+1;j++){ //重量为j的背包 if(j<w[i]){ //不拿 dp[i][j]=dp[i-1][j]; }else{ //拿或不拿 dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } } System.out.print(dp[n][m]); } }
方法二:一维dp表
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m=sc.nextInt(); //物品个数、背包最大重量 int[] w=new int[n+1]; int[] v=new int[n+1]; int[] dp=new int[m+1]; for(int i=1;i<n+1;i++){ w[i]=sc.nextInt(); v[i]=sc.nextInt(); } for(int i=1;i<n+1;i++){ //第i个物品 for(int j=m;j>=1;j--){ //重量为j的背包,要从后往前推,因为从前往后推会把上一条的dp[j-w[i]]记录给覆盖 if(j>=w[i]){ //j<w[i]放不下就不拿不更新dp表,j>=w[i]放得下就更新dp表 dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]); } } } System.out.print(dp[m]); } }
0.0分
5 人评分
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:689 |
数组输出 (C语言代码)浏览:767 |
C语言训练-计算一个整数N的阶乘 (C语言代码)浏览:933 |
WU-蓝桥杯算法提高VIP-Quadratic Equation (C++代码)浏览:1748 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1916 |
The 3n + 1 problem (C语言代码)浏览:504 |
淘淘的名单 (C语言代码)浏览:1226 |
1052题解(链表操作)浏览:668 |
字符逆序 (C语言代码)浏览:508 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:565 |