背包问题

背包问题跟昨天发表的硬币找零问题非常类似。

你获得一张免费超市购物券，它不限制你选择的物品金额，但是限制物品的容量，也就是给你一个指定大小的购物袋。

如何在指定容量的购物袋（背包）中挑选价值最高的物品？

假设超市里有音响、PC、吉他和iPod，它们的价值和体积如下所示，我们有一个大小为3的购物袋。

那我们该如何做出最佳选择呢？

与之前的硬币问题一样，我们选择一个商品时候会面临选择这个商品和不选择这个商品两种情况。

如果我们选择这个商品，那么当前最高价值就是没有选择这个商品的最高价值 + 当前商品的价值，当然我们需要考虑一个容量的问题

如果我们没有选择这个商品，那么当前最高价值就是之前的最高价值。

同样我们也需要考虑边界条件。

如果没有商品，那么最高价值永远是0
如果背包容量为0，那么最高价值也永远也是0
如果当前选择的商品体积大于背包剩余的容量，这个商品不应该放进背包中。

下面是我的推算过程：

代码如下：

 /**
     * 功能描述: 假设你有一个重量为packWeight的背包，商场有的商品为goods，
     * 你需要挑选一些商品使得背包中装的东西的价值最高
     * 假设不可以重复选择商品
     * @author lkb
     * @date 2019/6/3
     * @param goods 商品的信息
     * @param packWeight 背包重量
     * @return java.util.List<com.lkb.dp.problems.pack.Goods>
     */
    public static int packDP(Goods[] goods, int packWeight){
        int[][] value = new int[goods.length + 1][packWeight + 1];

        //背包的容量为0
        for(int i=0;i<goods.length + 1;i++){
            value[i][0] = 0;
        }
        //没有商品
        for(int i=0;i<packWeight+1;i++){
            value[0][i] = 0;
        }

        for(int weight=1; weight<packWeight+1; weight++){
            for(int good=1; good<goods.length + 1; good++){
                //商品的重量大于背包的容量
                if(goods[good-1].getWeight() > weight){
                    value[good][weight] = value[good-1][weight];
                    continue;
                }
                if(weight - goods[good-1].getWeight() >= 0){
                    if((value[good][weight - goods[good-1].getWeight()] + goods[good-1].getValue()) > value[good-1][weight] ){
                        //选择当前物品的价值大于不选择当前物品的价值
                        value[good][weight] = value[good][weight - goods[good-1].getWeight()] + goods[good-1].getValue();
                    }else{
                        //选择当前物品的价值小于不选择当前物品的价值
                        value[good][weight] =  value[good-1][weight];
                    }
                }
            }
        }
        return value[goods.length][packWeight];
    }

下面是简单递归的实现方式。

    /**
     * 功能描述: 假设你有一个重量为packWeight的背包，商场有的商品为goods，
     * 你需要挑选一些商品使得背包中装的东西的价值最高
     * 假设不可以重复选择商品
     * @author lkb
     * @date 2019/6/3
     * @param goods 商品的信息
     * @param packWeight 背包重量
     * @return java.util.List<com.lkb.dp.problems.pack.Goods>
     */
    public static int pack(Goods[] goods, int packWeight){
        int maxValue = 0;
        Map<Integer,List<Goods>> map = new HashMap<>();
        for(int i=0;i<goods.length;i++){
            int weight = packWeight - goods[i].getWeight();
            int value = goods[i].getValue();
            for(int j=0;j<goods.length;j++) {
                //只要背包的容量够，我们就应该尝试选择这个物品
                //后续再比较最大值
                if (weight - goods[j].getWeight() >= 0) {
                    value = goods[j].getValue() + value;
                    weight = weight - goods[j].getWeight();
                }
            }
            if(maxValue < value){
                maxValue = value;
            }
        }
        return maxValue;
    }

大家也可以在这个地址下载源码，或者关注我的公众号，一起见证我的成长。

欢迎关注我的公众号 -- 成长为大牛