背包问题

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();

}