解题思路:
注意事项:
参考代码:
import java.util.Scanner; public class 开心的金明 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt();//总价值 int n= sc.nextInt();//物品的数量 int i, j; int[] p = new int[n + 1]; int[] w = new int[n + 1]; int[][] dp = new int[n + 1][m + 1]; for (i = 1; i <= n; i++) { w[i] = sc.nextInt(); //每个东西的价格 p[i] = sc.nextInt();//满意度 p[i]*=w[i];//满意度×价格 } //后面就是背包问题了,参考01背包 for (i = 1; i <= n; i++) for (j = 1; j <= m; 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]] + p[i]); } } System.out.print(dp[n][m]); } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题9.3 (Java代码)浏览:965 |
大小写转换 (C语言代码)浏览:858 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:572 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:596 |
淘淘的名单 (C语言代码)浏览:1104 |
【金明的预算方案】 (C++代码)浏览:843 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:594 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:862 |
星期判断机 (C语言代码)浏览:859 |
罗列完美数 (C语言代码)浏览:491 |