解题思路:
注意事项:
参考代码:
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 人评分
求组合数 (C语言代码)浏览:1159 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:862 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1918 |
蛇行矩阵 (C语言代码)浏览:505 |
前10名 (C语言代码)浏览:727 |
格式化数据输出 (C语言代码)浏览:821 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:1001 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:679 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:553 |