解题思路:
注意事项:
参考代码:
import java.util.Scanner; /** * 2021年2月23日 下午5:37:46 * @author praguetramp * 01背包问题 */ public class P1924 { //w[]物品重量,v[]物品价值,n物品数量,m背包容积 private static int MaxValue(int w[],int v[],int n,int m) { //dp[n][m]表示前n件物品放在体积为m的背包下,形成的最大价值 int dp[][] = new int[n+1][m+1]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(w[i]>j) 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]); } return dp[n][m]; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n=in.nextInt(),m=in.nextInt(); int w[]=new int[n+1],v[]=new int[n+1]; for(int i=1;i<=n;i++) { w[i]=in.nextInt();v[i]=in.nextInt(); } int ans=MaxValue(w,v,n,m); System.out.println(ans); in.close(); } }
0.0分
0 人评分
时间转换 (Java代码)浏览:707 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:695 |
宏定义浏览:837 |
点我有惊喜!你懂得!浏览:1435 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1533 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:422 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:668 |
用筛法求之N内的素数。 (C语言代码)浏览:1257 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1058 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:475 |