解题思路:
物品i 1 2 3 4 5 背包j
1 0 3 3 3 3 背包体积一定要大于物品体积
2 0 3 5 5 8 如果背包的体积大于物品的体积,那么就是可以装的下,就把上一层的值与上一层值+物品价值,对比;
3 0 3 5 7 8 如果背包的体积小于物品的体积,那么就是装不下,就把上一层的数据给到这一层
注意事项:
参考代码:
import java.util.Scanner; public class Text08 { public static void main(String []args){ Scanner scanner=new Scanner(System.in); int n=scanner.nextInt();//物品的个数 int m=scanner.nextInt();//背包的重量 int []arr=new int[n+1];//物品的重量 int []arr1=new int[n+1];//物品的价值 for (int i = 1; i <=n; i++) { arr[i]=scanner.nextInt(); arr1[i]=scanner.nextInt(); } //现在的程序是,背包的容量不减,价值不加; //放在背包的物品是价值 int [][] dp=new int[n+1][m+1]; //控制物品重量 for (int i = 1; i <=n; i++) { //控制背包 for (int j = 1; j <=m; j++) { //背包小于物品的重量 if (j>= arr[i]) { dp[i][j]=Math.max(dp[i-1][j],dp[i][j-arr[i]]+arr1[i]); } else { dp[i][j]=dp[i-1][j]; } } } System.out.println(dp[n][m]); } }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:664 |
C语言训练-素数问题 (C语言代码)浏览:1660 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:587 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:702 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:576 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:678 |
1642题解浏览:715 |
回文数字 (C语言代码)浏览:2510 |
淘淘的名单 (C语言代码)浏览:1228 |
数列排序 (C语言代码)浏览:616 |