贪心算法之阿里巴巴与四十大盗——背包问题

14天阅读挑战赛

        有一天，阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时，远处突然出现一股烟尘，弥漫着向上空飞扬，朝他这儿卷过来，而且越来越近。阿里巴巴心里害怕，担心碰到的是一伙儿强盗，他赶紧把毛驴赶到丛林的小道里，自己爬到一棵大树上躲了起来，这棵大树生长在一个大石头旁边。靠近以后，他才看清原来是一支马队，他们共有四十人，一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋 ，他从丛林中来到那个大石头跟前，喃喃地说道：“芝麻，开门吧！”随着那个头目的喊声，大石头前突然出现一道宽阔的门路，于是强盗们鱼贯而入。阿里巴巴躲在树上观察他们，直到他们走得无影无踪之后，才从树上下来。 他大声喊道：“芝麻，开门吧！”他的喊声刚落，洞门立刻打开了。他小心翼翼地走了进去，一下子惊呆了， 洞中堆满了财物，还有多得无法计数的金银珠宝，有的散堆在地上，有的盛在皮袋中。突然看见这么多的金 银财宝，阿里巴巴深信这肯定是强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界，见识一下这些宝物，他想一种宝物只拿一个，如果太重就用锤子凿开，但毛驴的运载能力是有限的，怎么才能用毛驴运走价值最大的财宝分给乡亲们呢？

        阿里巴巴陷入沉思……

背包问题

        有n种物品，每种物品只有一个，第i种物品的重量为w，价值为v，背包的容量为W，物品可以分割。如何放置物品，使装入背包的物品价值之和最大？

问题分析

        本题为可分割背包问题，可以尝试贪心策略。

        （1）每次选择价值最大的物品装入背包。

        （2）每次选择重量最小的物品装入背包。

        （3）每次选单位重量价值最大的物品装入背包。

        思考一下，如果选价值最大的物品，但重量非常大，则可能一个也装不下，分割一部分装入，价值未必 是最高的；如果选重量最小的物品装入，则其价值不一定高，所以在总重量受到限制的情况下无法保证价值 最大；而如果每次选单位重量价值最大的物品，则装满背包后一定能得到最大价值。

         因此，应采用第3种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。

算法设计

        （1）确定合适的数据结构并初始化。首先将物品的重量、价值和单位重量价值定义为一种结构体类 型，然后对物品按单位重量价值从大到小进行排序。

        （2）根据贪心策略，按照单位重量价值从大到小选取物品，直至达到背包容量。如果在装入第i个物品 时超出背包容量，则取该物品的一部分装入背包。

完美图解

        物品的价值和重量如表 2-3 所示。如果背包容量 W=30，怎么才能装入最大价值的物品？

        表2-3 物品清单

         （1）贪心策略是每次选单位重量价值（价值/重量）大的物品，因此可以按单位重量价值对物品进行降 序排列，排序后的物品清单如表2-4所示。

表2-4 排序后的物品清单

 （2）按照贪心策略，每次选择单位重量价值大的物品装入背包。

        ● 第1次选择2号物品，剩余容量为30−2=28，当前已装入物品的最大价值为8。

        ● 第2次选择10号物品，剩余容量为28−5=23，当前已装入物品的最大价值为8+15=23。

        ● 第3次选择6号物品，剩余容量为23−8=15，当前已装入物品的最大价值为23+20=43。

        ● 第4次选择3号物品，剩余容量为15−9=6，当前已装入物品的最大价值为43+18=61。

        ● 第5次选择5号物品，剩余容量为6−5=1，当前已装入物品的最大价值为61+8=69。

        ● 第6次选择8号物品，此时剩余容量为1，而8号物品的重量为4，无法全部装入，8号物品的单位重量价值为1.5，因此装入价值1x1.5=1.5，此时已装入物品的最大价值为69+1.5=70.5，剩余容量为0，背包已装满。

（3）构造最优解。

        把这些已装入物品的序号组合在一起，即可得到最优解(2，10，6，3，5，8)，其中最后一个物品为部分装入(8号物品装了1/4)，已装入物品的最大价值为70.5。

算法详解

        （1）确定合适的数据结构。

定义结构体

private static class Goods {
    //商品i
    private int goods_i;
    //商品重量
    private double goods_weight;
    //商品价值
    private double goods_value;
    public Goods(int goods_i, double goods_weight, double goods_value) {
        this.goods_i = goods_i;
        this.goods_weight = goods_weight;
        this.goods_value = goods_value;
    }
    public double getGoods_weight() {
        return goods_weight;
    }
    public double getGoods_value() {
        return goods_value;
    }
}

用集合存储物品清单中的数据

    private static List mList = new ArrayList<>();
    private static void initData() {
        mList.add(new Goods(1, 4, 3));
        mList.add(new Goods(2, 2, 8));
        mList.add(new Goods(3, 9, 18));
        mList.add(new Goods(4, 5, 6));
        mList.add(new Goods(5, 5, 8));
        mList.add(new Goods(6, 8, 20));
        mList.add(new Goods(7, 5, 5));
        mList.add(new Goods(8, 4, 6));
        mList.add(new Goods(9, 5, 7));
        mList.add(new Goods(10, 5, 15));
    }

        （2）对物体单位重量价值进行排序。

//按照单位重量价值从大到小排（冒泡算法）
Goods good = null;
for (int i = 0; i < mList.size() - 1; i++) {
    for (int j = 0; j < mList.size() - i - 1; j++) {
        //单位重量价值的商品（v/w）
        double agoValue = mList.get(j).getGoods_value() / mList.get(j).getGoods_weight();
        double afterValue = mList.get(j + 1).getGoods_value() / mList.get(j + 1).getGoods_weight();
        if (agoValue < afterValue) {
            good = mList.get(j);
            mList.set(j, mList.get(j + 1));
            mList.set(j + 1, good);
        }
    }
}

for (int i = 0; i < mList.size(); i++) {
    double value = mList.get(i).getGoods_value() / mList.get(i).getGoods_weight();
    System.out.println("good:" + new Gson().toJson(mList.get(i)) + ", 单位重量价值:" + value);
}
 
//输出日志：good:{"goods_i":2,"goods_weight":2.0,"goods_value":8.0}, 单位重量价值:4.0
//         good:{"goods_i":10,"goods_weight":5.0,"goods_value":15.0}, 单位重量价值:3.0
//         good:{"goods_i":6,"goods_weight":8.0,"goods_value":20.0}, 单位重量价值:2.5
//         good:{"goods_i":3,"goods_weight":9.0,"goods_value":18.0}, 单位重量价值:2.0
//         good:{"goods_i":5,"goods_weight":5.0,"goods_value":8.0}, 单位重量价值:1.6
//         good:{"goods_i":8,"goods_weight":4.0,"goods_value":6.0}, 单位重量价值:1.5
//         good:{"goods_i":9,"goods_weight":5.0,"goods_value":7.0}, 单位重量价值:1.4
//         good:{"goods_i":4,"goods_weight":5.0,"goods_value":6.0}, 单位重量价值:1.2
//         good:{"goods_i":7,"goods_weight":5.0,"goods_value":5.0}, 单位重量价值:1.0
//         good:{"goods_i":1,"goods_weight":4.0,"goods_value":3.0}, 单位重量价值:0.75

        （3）使用贪心算法求解问题

        在单位重量价值排序的基础上，使用贪心算法求解问题。如果当前物品的重量小于或等于剩余容量，则可以装入，将剩余容量减去当前物品的重量，同时将已装入物品的价值加上当前物品的价值。如果当前物品的重量大于剩余容量，则表示不可以全部装入，但可以部分装入，直到背包装满，将剩余容量乘以当前物品的单位重量价值，与已装入物品的价值相加，即为已装入物品的最大价值。

//物品的总价值
private static double solve(List list) {          
    double W = 30;                                       //背包总容量
    double sum = 0.0;                                    //sum表示已装入物品的价值之和
    double cleft = W;                                    //背包的剩余容量
    for (int i = 0; i < list.size(); i++) {              //使用贪心算法求解问题
        if (list.get(i).getGoods_weight() <= cleft) {    //如果物品的重量小于或等于剩余容量
            cleft -= list.get(i).getGoods_weight();
            sum += list.get(i).getGoods_value();
        } else {                                         //如果物品的重量大于剩余容量
            double p = list.get(i).getGoods_value() / list.get(i).getGoods_weight();
            sum += cleft * p;                            //部分装入
            break;
        }
    }
    return sum;
}

double solve = solve(mList);
System.out.println("solve：" + solve);
//输出日志：solve：70.5