解题思路:
简单的0-1背包问题。
注意事项:
注意第二层循环时,j要从m到weight[i]依次递减下去。不然会出现同一物品被选多次的场景。(该种情况是完全背包的解题方法)
参考代码:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] s = reader.readLine().split(" "); int n = Integer.parseInt(s[0]);//物品的个数 int m = Integer.parseInt(s[1]);//背包的重量 int[] weight = new int[n + 1]; int[] value = new int[n + 1]; for (int i = 1; i <= n; i++) { String[] s1 = reader.readLine().split(" "); weight[i] = Integer.parseInt(s1[0]); value[i] = Integer.parseInt(s1[1]); } int dp[] = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = m; j >= weight[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } System.out.println(dp[m]); } }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:439 |
数组输出 (C语言代码)--此题的题目描述有问题浏览:1816 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:865 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:580 |
母牛的故事 (C语言代码)浏览:715 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:562 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:585 |
大神老白 (C语言代码)浏览:600 |
矩阵转置 (C语言代码)浏览:782 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:567 |