01背包问题

介绍

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

分析

优化后的代码 

public class demo {
    static class Item{
        int index;
        String name;
        int weight;
        int value;
        Item(int index,String name,int weight,int value){
            this.index=index;
            this.name=name;
            this.weight=weight;
            this.value=value;
        }
    }

    public static void main(String[] args) {
        //对象数组
        Item[] items = new Item[]{
                new Item(1,"黄金",4,1600),
                new Item(2,"宝石",8,2400),
                new Item(3,"白银",5,30),
                new Item(4,"钻石",1,10_000),
        };
        System.out.println(select(items,10));
    }
    public static int select(Item[] items,int total){
        //dp数组临时存储
        int[] dp = new int[total+1];
        //拿到第一行item对象黄金处理
        Item item0 = items[0];
        for (int i = 0; i < total+1 ; i++) {
            if (i >= item0.weight) {
                dp[i] = item0.value;
            }else {
                dp[i]=0;
            }
        }
        System.out.println(Arrays.toString(dp));
        //其余item处理
        for (int i = 1; i < items.length ; i++) {
            Item item = items[i];
            //内部必须从右往左计算  使用一维数组时
            for (int j = total; j >=0  ; j--) {
                if (j >= item.weight) { //装得下，比较当前价值+剩余容量能装下价值  VS 上一行对应列的价值
                    dp[j] = Math.max(item.value+dp[j-item.weight],dp[j]);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[total];
    }
}

运行结果