Java同学看过来

题目描述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

10 100
5 8
32 47
17 43
7 9
6 4
29 40
2 6
14 31
6 17
1 3

package 背包问题;

import java.util.Scanner;

public class completeBackpack {
    public static int completeBag(int[] weight, int[] value, int bagWeight) {
        int num = weight.length;
        int[][] dp = new int[num + 1][bagWeight + 1];

        for (int i = 1; i <= num; i++) {
            for (int j = 0; j <= bagWeight; j++) {
                for (int k = 0; k * weight[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * weight[i - 1]] + value[i - 1] * k);
                }

            }

        }
//        for (int[] ints : dp) {
//            for (int j = 0; j < dp[num].length; j++) {
//                System.out.print(ints[j] + " ");
//            }
//            System.out.println();
//        }
        return dp[num][bagWeight];
    }

    public static int completeBagOptimization(int[] weight, int[] value, int bagWeight) {
        int num = weight.length;
        int[][] dp = new int[num + 1][bagWeight + 1];

        for (int i = 1; i <= num; i++) {
            for (int j = 0; j <= bagWeight; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= weight[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
                }
            }

        }
//        for (int[] ints : dp) {
//            for (int j = 0; j < dp[num].length; j++) {
//                System.out.print(ints[j] + " ");
//            }
//            System.out.println();
//        }
        return dp[num][bagWeight];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int itemsNumber = sc.nextInt();
        int bagWeight = sc.nextInt();
        int[][] arr = new int[itemsNumber][2];
        int[] weight = new int[itemsNumber];
        int[] value = new int[itemsNumber];
        for(int i = 0; i < itemsNumber; i++) {
            for(int j = 0; j < 2; j++) {
                arr[i][j] = sc.nextInt();
            }
            weight[i] = arr[i][0];
            value[i]=   arr[i][1];
        }
        System.out.println(completeBagOptimization(weight, value, bagWeight));
    }
}