有N件物品和一个容量为V的背包。第i件物品的价值是C[i],重量是W[i]。求解将哪些物品装入背包可使价值总和最大。
输入第一行数 N V (1 <=N <=500) (1<= V <= 10000)
输入 N行 两个数字 代表 C W (1 <= C <= 50000, 1 <= W <=10000)
输出最大价值
5 10 8 6 10 4 4 2 5 4 5 3
19
1 1 10 2
0
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // n件物品 int v = sc.nextInt(); // 容量v int[] c = new int[n]; // 单件价值 int[] w = new int[n]; // 单间重量 for (int i = 0; i < n; i++) { c[i] = sc.nextInt(); w[i] = sc.nextInt(); } // int[][] dp = new int[n][v]; // 初始化第一行 for (int i = 0; i < v; i++) { if (i >= w[0]) { dp[0][i] = w[0]; } else { dp[0][i] = 0; } } // 遍历物品 for (int i = 1; i < n; i++) { // 遍历容量 for (int j = 0; j < v; 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]] + c[i]); } } } System.out.println(dp[n-1][v-1]); sc.close(); }