贪心

概念¶

“A greedy algorithm looks for “good solutions”, called local optima , which will hopefully lead to the correct final solution, called the global optimum .

Greedy 思想¶

在对问题求解时，总是做出在当前看来是最好的选择。
局部最优，对整体求解更加有利。
贪心算法 vs 动态规划算法：
- 动态规划算法 通常自底向上的求解各子问题；
- 贪心算法 则通常自顶向下进行，迭代的作出贪心选择，每次贪心选择就将所求问题简化为规模更小的子问题。

弊端¶

当前最好选择
不考虑整体，只考虑局部最优解
可能不能得到整体最优解，其最终结果可能是最优解的很好近似。

哪些适合贪婪算法¶

只有局部最优策略能产生全局最优策略的情况
选择的贪心策略必须具备无后效性

例题¶

253. 订会议室¶

贪婪算法，会议按照起止时间进行
先看有无空会议室
有则开会，无则订一间新的

/**
 * @param: intervals 所有会议的起止时间
 * [{ start, end }, ...]
*/
function minMeetingRooms(intervals) {
  if (!intervals || intervals.length === 0) {
    return 0;
  }

  // 1. 会议：按照开始时间排序
  intervals.sort(function comparator(a, b) { return a.start - b.start; });

  // 2. 会议室：用最小堆来维护会议室，按照结束时间排序
  const heap = new PriorityQueue(intervals.length, function comparator(a, b) { return a.end - b.end; });

  // 3. 让第一个会议在第一个会议室进行
  heap.offer(intervals[0]);
  if(let i = 0; i < intervals.length; i++) {
    // 4. 从第二个会议开始，每个会议都从最小堆中取出一个会议室
    let interval = heap.poll();
    if (intervals[i].start >=  interval.end) {
      // 5. 若当前会议可以等会议室的会议结束后开始，则可以重复利用会议室
      interval.end = intervals[i].end;
    } else {
      // 6. 否则，开辟新的会议室
      heap.offer(intervals[i]);
    }
    // 7. 将旧的会议室，也放回最小堆里
    heap.offer(intervals[i]);
  }

  // 8. 最小堆里会议室个数为所需最少会议室
  return heap.size(); 
}

硬币问题¶

硬币问题 (Coin-changing Problem)：
现有面值25美分、10美分和1美分三种面值硬币，要将63美分换成零钱，按照贪心算法该怎么换？

function makeChange(origAmt) {
  var remainAmt = 0;
  if (origAmt % 25 < origAmt) {
    console.log("25-cent coins: ", parseInt(origAmt / 25));
    origAmt = origAmt % 25
  }
  if (origAmt % 10 < origAmt) {
    console.log("10-cent coins: ", parseInt(origAmt / 10));
    origAmt = origAmt % 10
  }
  console.log("1-cent coins: ", parseInt(origAmt / 1));
}

部分背包问题¶

部分背包问题 (Fractional Knapsack Problem)：
按照贪心算法，每次选 性价比最高 的物品放入背包。
算法步骤：
- 1) 背包拥有容量 capacity ，物品拥有价值 value 和大小size。
- 2) Rank items by value/size ratio.
- 3) Consider items in terms of decreasing ratio.
- 4) Take as much of each item as possible.

function ksack(capacity, n, size, value){
  // 冒泡排序, value/size递减
  for(var i = 0; i < n; i++){
    for(var j = 0; j < n-i-1; j++){
      if(value[j]/size[j] < value[j+1]/size[j+1]){
        var tmp = value[j];
        value[j] =  value[j+1];
        value[j+1] = tmp;
        tmp = size[j];
        size[j] =  size[j+1];
        size[j+1] = tmp;
      } 
    } 
  } 
  //console.log({value, size})

  let load = 0, result = 0;
  for(let i = 0; load < capacity && i < n; i++){
    if(size[i] <= capacity - load){
      load += size[i];
      result += value[i];
    }
  }

  return result;
}