01背包问题用动态规划

Question

0-1背包问题是很经典的算法问题：给定n种物品和一背包。物品i的重量是wi，价值是vi，背包最大容量是C。应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？
样列1：
输入： 物品数：3
背包成重量：25
每个物品重量：[20,15,10]
每个物品价值：[25,30,20]
输出： 最大价值：50
此时包中装了第2、3件物品

我已经写了方法，想要主方法补写一下

Answer 1

public class Knapsack {
    public static int knapsack(int[] w, int[] v, int C) {
        int n = w.length;
        int[][] dp = new int[n + 1][C + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= C; j++) {
                if (j < w[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                }
            }
        }
        return dp[n][C];
    }

    public static void main(String[] args) {
        int[] w = {20, 15, 10};
        int[] v = {25, 30, 20};
        int C = 25;
        int maxVal = knapsack(w, v, C);
        System.out.println("最大价值：" + maxVal);
    }
}