1. 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利的选择， 从而希望能够导致结果是最好或者最优的算法
  2. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

集合覆盖问题

image.png

  1. function getMinLeitai (boardcasts) {
  2.   const allAreas = new Set();
  3.   [...boardcasts.keys()].forEach(key => {
  4.     boardcasts.get(key).forEach(item => allAreas.add(item))
  5.     });
  7.   const selects = []
  8.   let tempArr = []
  9.   let maxKey = null
  10.   while (allAreas.size > 0) {
  11.     maxKey = null
  12.       for (item of boardcasts) {
  13.       tempArr = item[1].filter(val => allAreas.has(val))
  14.       if (tempArr.length && (maxKey === null || boardcasts.get(maxKey).length < tempArr.length)) {
  15.         maxKey = item[0]
  16.       }
  17.     }
  18.     if (maxKey !== null) {
  19.       selects.push(maxKey)
  20.       boardcasts.get(maxKey).forEach(val => allAreas.delete(val))
  21.     }
  22.   }
  23.   return selects
  24. }
  26. var map = new Map()
  27. map.set('k1', ['北京', '上海', '天津'])
  28. map.set('k2', ['广州', '北京', '深圳'])
  29. map.set('k3', ['成都', '上海', '杭州'])
  30. map.set('k4', ['上海', '天津'])
  31. map.set('k5', ['杭州', '大连'])
  33. console.log(getMinLeitai(map).join(', '))

最少硬币找零

  1. function minCoinChange(coins, amount) {
  2.   const change = [];
  3.   let total = 0;
  4.   coins.sort((a, b) => b - a); // 贪心算法体现
  5.   for (let i = 0; i < coins.length; i++) {
  6.     const coin = coins[i];
  7.     while (total + coin <= amount) {
  8.       change.push(coin);
  9.       total += coin;
  10.     }
  11.   }
  12.   return change;
  13. }
  15. console.log(minCoinChange([1, 2, 10, 5], 26).join(', '))