贪心算法

贪心算法是一种遵循近似解决问题的技术,通过每个阶段的局部最优选择(当前最好解),从而达到全局的最优解,它不像动态规划,计算更大的格局

1. 最少硬币找零问题

这个算法很简单,就是对每个硬币面额(从大到小),把它的值累加后,判断是否小于找零的值,小于则再拿这个面值的硬币,否则就拿第二面值的硬币,直到等于找零的值为止

这样就可以拿更多面值大的硬币

function MinCoinChange(coins) { 
  var coins = coins 
  return makeChange = function(amount) { 
    var change = [],
        total = 0;
    for(let i = coins.length;i>=0;i--) { 
      let coin = coins[i]
      while(total + coin <= amount) { 
        change.push(coin)
        total += coin 
      }
    }
  }
}

2. 分数背包问题

求解分数背包问题的算法与动态规划的版本不同,在0-1背包问题中,只能向背包中转入完整的物品,而在分数背包问题中,我们可以转入分数的物品

我们看看贪心算法的解决方式

function knaepSack(capacity ,values,weights ) { 
  let n = values.length,
      load = 0, // 当前负重
      val = 0   // 当前价值
  
  // 如果当前重量小于capacity 继续迭代
  for(let i =0;i< n && load < capacity;i++) { 
    // 如果放得下当前物品 则直接加上去
    if(weights[i] <= (capacity - load )) { 
      val += values[i]
      load += weights[i]
    } else { 
      // 否则,计算还能放入物品的百分数
      let r = (capacity -load ) /weights[i]
      // 加上物品比例价值
      val += r * values[i]
      load += r * weights[i]
    }
  }
  return weights
}

很明显,这并不是最优解