最优组合问题 - 贪心算法

周末时间基本都在带娃，断更了一段时间，难得有点时间还是得有毅力坚持写，坚持总结。



最近公司在拓展电商相关业务，其中一个环节是物流发货。物流打包环节有一个需求是希望能给运营同事一个小工具能快速计算最优的包裹组合。



我们这里不关注过多业务细节，只是把这个问题抽象总结一下。



问题：

假设我们有如下4种规格的包裹可供选择:



由于我们的货物是抛货, 所以只考虑给定任意总Size的的打包需求，能得到最优的包裹组合。

抛重：即是体积重，

1、当实重大于体积重，就属于重货，按实重计费度；

2、当体积重大于实重就叫抛货，按体积重计费；



这里最优的标准比较简单：包裹个数最少，同时也是总运费最低。



例如，我需要发153个货，那么最优的就是Package XL 1 + Package M 1。



贪心算法



很符合直觉的策略是先尽可能选大的包裹，先从小号开始匹配，小号的装不下就升级大一号的包裹，直到能装下或者没有更大的箱子了，依次类推。例如总共要装箱150个，那么:

• 先用Package S 发现装不下，

• 升级成Package M也装不下，

• 继续升级成Package L也装不下，

• 继续升级成Package XL也装不下，但是没有更大的选择了，所以（贪心）打包一次。更新待装箱的商品数据量 = 150 - 120 = 30；



这样每次一个周期结束，再次用剩余没装箱的数量继续这样做打包操作:

• 先用Package S 发现装不下，

• 升级成Package M发现能装下了，所以打包一次。更新待装箱的商品数据量 = 30 - 40 <= 0；



总结上述过程，我们发现每次迭代打包本质都是把当前需要求解的问题分成了一个子问题，每次解决子问题的策略都是尽量优先用最大的箱子，且任意子问题是不依赖上次迭代的结果。可以理解为每次迭代无非是传入了一个新的需要打包的产品数量，这样就能每次迭代都是朝着问题的最终解进了一步。



贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即每次贪心决策不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。



所以贪心策略适用的前提是，局部最优策略能最终产生全局最优解。也就是当算法终止的时候，局部最优正好就是全局最优。



实现

由于只是单纯的计算，不需要持久化业务的数据，如果把计算业务逻辑写在后端每次API调用也比较耗时，所以我索性直接用JS把计算代码也撸了。



计算代码：

  function minPackageCal(packages, amount) {
    let minimumUnit = Number.MAX_SAFE_INTEGER;
    let maximumUnit = 0;
    let packageMap = new Map();
    for (let i = 0; i < packages.length; i++) {
      packageMap.set(packages[i], 0);
      minimumUnit = Math.min(packages[i], minimumUnit);
      maximumUnit = Math.max(packages[i], maximumUnit);
    }
    let packageResult = [];
    let totalPacked = 0;
    while (totalPacked < amount) {
      for (let i = 0; i < packages.length; i++) {
        var packageUnit = packages[i];
        if(packageUnit > amount - totalPacked || packageUnit === maximumUnit){
          packageResult.push(packageUnit);
          packageMap.set(packageUnit, packageMap.get(packageUnit)+1);
          totalPacked += packageUnit;
          break;
        }
      }
    }
    return packageMap;
  }



调用代码：

    //given package types
    const packageTypes = [20, 40, 80, 120];
    
    //amountInputValue should be data binding with the input box    
    var result = minPackageCal(packageTypes, amountInputValue);



最终实现的效果：



贪心的局限性



在这里例子中，由于可供选择的包裹条件限制，我们使用贪心算法得出来的局部最优解恰好是全局最优解。但是如果我们换一个包裹组合阵型就不一定了，

比如：

假设今天我们的包裹Package M做了推广特价，从6.99€ 打折到3.99€，那么按照贪心我们不一定能得到最佳的组合了:



如果局部最优不是全局最优，那么就不能用贪心算法，可以考虑用动态规划来解决这类最优解问题。



欢迎关注我的公众号：好奇心森林