01背包问题-ag真人游戏

介绍

有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];
    }
}

运行结果