0-1背包

public class beibao {
    public static void main(String[] args) {
        // 物品重量和价值
        int[] weights = {5,6,10,9};
        int[] values = {200,66,100,72};
        // 背包容量
        int large = 15;
        // 存放数量
        int count = 4;

        System.out.println("背包容量：" + large + "，携带物品数量：" + count);
        int maxValue = method(count, large, weights, values);
        System.out.println("最大价值：" + maxValue);
    }

    public static int method(int count, int large, int[] weights, int[] values){
        int[][] dp = new int[count+1][large+1];

        // 携带商品个数依次增加
        for(int i=1; i<=count; i++){
            int weight = weights[i-1];
            int value = values[i-1];
            // 背包容量依次增加
            for(int j=1; j<=large; j++){
                if(j<weight){
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight]+value);
            }
        }
/*
        // 遍历dp
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
*/
        return dp[count][large];
    }
}