当前位置：首页>Excel>一个excel中贪心算法的装箱问题

一个excel中贪心算法的装箱问题

2026-08-11 01:31:52

一个excel中贪心算法的装箱问题

Hi，大家好，我是突袭者

今天我们分享一个比较烧脑的excel问题，下表中的A~B列是数据源，第1列为标签名，第2列为对应的数量。

问题要求

要求每12个标签装为一箱，先同标签装箱，如果有剩余，则最多可以有两类标签混装在同一箱，同时要求整体所用的箱数最少，D~E列为一组可能的结果。

这个问题的结果不是唯一的，但是最后的总箱数是唯一的，举个简单的例子：

A—13；B—13；C—2。

首先A和B分别各自拿出12个分别装在一箱，这个时候A和B都剩余1个，因为最多两个标签混装，那么，A剩余的1个可以和C混装或者B剩余的1个也可以和C混装，这样就出现了两种结果，但是总箱数都是3箱。

回到最初的问题上来，这是一个典型的贪心算法问题：只要优先把需要混装的剩余数量最多的标签依次装箱（不论和谁混装）即可实现箱数最优。

什么是贪心算法？

贪心算法（Greedy Algorithm）：它就像是在人生的每一个岔路口，都只选择当下看起来最好的那条路，且绝不回头。

核心特点是在每一步决策中都采取当前最优（局部最优）策略，以期最终获得全局最优的算法。它不回溯，也不考虑未来的影响。

什么时候可以用贪心算法呢？

全局最优解可以通过一系列的局部最优解得到，这是贪心算法可行的基石。
一个问题的最优解包含了子问题的最优解，也就是说，如果你把问题切开，一个个子问题的最优解合并在一起就是全局最优解。
某个状态以前的过程不会影响以后的状态，只与当前状态有关。

既然要求每12个标签装为一箱，我们先将每个标签种类按照每12个来进行拆分，比如标签A的数量是33，可以拆分为2个12和一个9，其他的标签种类按此拆分。

拆分了之后，我们按照拆分后的数量降序排列(12的数量排在前面，不足12需要混装的排在后面)，得到一个新的数据集。

我们取数据集的第一行和最后一行，如果两个加起来数量大于12，则第一行的数据独立成为一箱。然后将这一行的数据从数据集中删除，继续判断；如果两个加起来小于等于12，则将这两行的数据装在一个箱子中，然后将这两行数据从数据集中删除，继续判断。

直到数据集剩下最后一行数据或者不剩下数据，如果剩下最后一行数据，则这一行独立成箱，递归结束；如果不剩下数据，则递归结束。

D1单元格函数公式：

=LET(_r1,TEXTSPLIT(CONCAT(REPT(A2:A7&"-12|",INT(B2:B7/12))&IF(MOD(B2:B7,12),A2:A7&"-"&MOD(B2:B7,12)&"|","")),"-","|",1),_r2,SORT(HSTACK(INDEX(_r1,,1),TAKE(_r1,,-1)*1),2,-1),fx,LAMBDA(self,_d,_acc,LET(_first,TAKE(_d,1),_last,TAKE(_d,-1),IF(ISERR(ROWS(_d)),_acc,IF(ROWS(_d)=1,VSTACK(_acc,_d),IF(SUM(_first,_last)>12,self(self,DROP(_d,1),VSTACK(_acc,_first)),self(self,DROP(DROP(_d,1),-1),VSTACK(_acc,HSTACK(@_first&"/"&@_last,SUM(_first,_last))))))))),fx(fx,_r2,{"标签组合","数量"}))