import java.util.Scanner; public class Main { public static void main(String[] ages) { Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int [] v=new int [m+1]; int [] p=new int [m+1]; int [] q=new int [m+1]; int [][]dp=new int [m+1][n+1]; for (int i = 1; i <= m; i++) { v[i]=scanner.nextInt();//价格 p[i]=scanner.nextInt();//重要度 q[i]=scanner.nextInt();//附件 p[i]*=v[i];//价格*重要度 //是否是附件 if (q[i]!=0) { p[i]+=p[q[i]];//当前附件的乘积加上主件的乘积 v[i]+=v[q[i]];//加上主件的价值 } } //01背包 for (int i = 1; i <= m; i++) { for (int j = 1; j j) { dp[i][j]=dp[i-1][j]; } else { dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-v[i]]+p[i]); } } } System.out.println(dp[m][n]); } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:512 |
Pascal三角 (C语言代码)浏览:1189 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:514 |
1009题解浏览:752 |
1642题解浏览:716 |
字符串输入输出函数 (C语言代码)浏览:2495 |
简单的a+b (C语言代码)浏览:950 |
一元一次方程 (C语言代码)浏览:4069 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:649 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:481 |