0-1 背包问题——贪心法求解

[weijieblog]

问题描述

背包问题是一类非常经典的组合优化问题的统称，我青葱年少时，曾对这个问题着迷。而我企图在百度上搜索这个问题的答案时，被无数数学语言弄得差点连问题都看不懂。尽管数学是美的，但为了不让大家叉掉我的博客。我将换种方式来描述这个问题，那么，这个问题就变成了老板请吃饭问题。

老板请吃饭问题描述

很久很久以前，有一个如你我般忠厚善良的可爱码农，在连续加班大半年以后，老板终于看到了他人性的光辉，决定请他吃晚餐。下班后，他们来到一个餐馆，餐馆的服务员给了他们如下一份菜单，老板让码农随意点菜，但不要重复点。而他们只能吃下 30 两重的东西，多吃一两都会胃炸裂而亡。那么问题来了，这位可爱的码农在不吃死的情况下，最多能花掉老板多少钱，如何点菜可以到达这个数目呢？

  // 以下是他们所能吃的东西的上限和菜单
  var capacity = 30,
      collections = [
        {name: '米饭'       , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

贪心法的解题思路

码农看着菜单思索，由于连续加班太久，一下想不出好的法子，突然他的第二人格冒出来跟他说，快用贪心法！

贪心法跟其他解决此类问题的算法比起来，是一种速度很快的算法，缺点就是它未必总能得到最优解。但由于其速度快而且简单，在很多地方还是很讨喜的。

贪心法的一般求解步骤：

1. 将问题分解为子问题。
2. 根据贪心策略求逐个解决子问题。

在这里问题是 如何点菜可以让老板花更多的钱 ，子问题就是 这道菜我该不该点。有了这样的一个子问题码农就可以遍历整个菜单，对着菜单上面的每一个菜做点或是不点的判断了。

而贪心策略在这个问题里有三种选择：

1. 总是挑份量最少的菜点。
2. 总是挑价格最贵的菜点。
3. 总是挑性价比（价格／份量）最高的菜点。

直觉告诉他，第三种策略比较容易让老板多掏钱，于是他采用第三种策略。

那么程序的流程就出来了：

1. 将菜单中的菜根据其性价比由高往低排序。
2. 按照性价比从高往低的顺序遍历排好序的菜单，碰到一个菜点一个菜。
3. 如果碰到这样一道菜，当点下该菜，所点菜的份量总合就会超过两人饭量上限的时候，跳过这道菜。
4. 遍历完菜单后，给出结果。

贪心法解决 0-1 背包问题的代码

  // 以下是他们所能吃的东西的上限和菜单
  var capacity = 30,
      collections = [
        {name: '米饭'        , weight: 7,  price: 10}, 
        {name: '宫保鸡丁'    , weight: 6,  price: 40}, 
        {name: '紫菜蛋花汤'  , weight: 12, price: 30}, 
        {name: '水煮牛肉'    , weight: 10, price: 50}, 
        {name: '海鲜蒸蛋'    , weight: 8,  price: 35}, 
        {name: '炭烤生蚝'    , weight: 2,  price: 40}, 
        {name: '白灼时蔬'    , weight: 5,  price: 30}
      ]

  var knapsackProblemByGreedy = function (collections, capacity, sortBy) {
    // 获得排好序的菜单
    var collections = sortBy(collections),
        result = {
          totalPrice: 0,
          totalWeight: 0,
          selected: []
        },
        currentWeight = 0  // 记录已点的菜的总重量

    // 遍历排好序的菜单
    collections.forEach(function (collection) {
      var temp = currentWeight + collection.weight
      // 如果点下当前的菜，菜的重量总和会超过两人的饭量总和（capacity）的值
      // 则程序不会进入下面的 if 语句去修改结果（result）的值
      currentWeight = temp <= capacity ? temp : currentWeight 
      if (currentWeight === temp) {
        result.totalPrice += collection.price
        result.totalWeight += collection.weight
        result.selected.push(collection)
      }
    })
    return result
  }

  // 将菜单按照性价比排序
  var sortByCostPerformance = function (collections) {
    // 这里的 slice(0) 是希望生成一个排序后的副本，而不是在原来的数组上做排序操作
    return collections.slice(0).sort(function (a, b) {
      return (b.price / b.weight) - (a.price / a.weight)
    })
  }

  console.log(knapsackProblemByGreedy(collections, capacity, sortByCostPerformance))

运行上面的代码就可以在控制台中看到结果，如果喜欢，可以把其他两种贪婪策略应用到程序中，看看不同的策略会对程序照成何种影响（完）。