请教一个python的凑整箱问题

Question

业务如下：
有仓库A、B、C
每个仓库中有数箱矿泉水，箱子中的矿泉水数量不一，如何将不满的数个箱子凑成满的？
例如：
满箱为24瓶
A库中有A-1 = 21瓶,A-2 = 15瓶,A-3 = 13瓶
B库中有B-1 = 4瓶，B-2 = 8瓶， B-3 = 23瓶
C库中有C-1 = 11
按照人类的逻辑应该是把A-3搬到A-1和A-2中间，然后从 A-3中拿出3瓶给A-1 再拿出9瓶给A-2 这样正好两整箱零1个
然后再把剩余的1瓶拿给B-3凑成一整箱
再将B-1和B-2组成半箱拿给C-1凑成23瓶

最终的要求就是出一张表告诉库管员从哪个箱子里拿多少瓶放到哪个箱子里，请问这种业务应该怎么实现？
试了下循环模拟计算，非常耗资源，像这种问题是否有更高效的算法去解决呢？

Answer 1

这样其实会有一些条件不是很明确.不知道你怎么算的.
下边是我的思路,如果不考虑不同仓库,假设了任意两个箱子之间流通成本是一样的.
从当前最少的那个箱子里取水放到最多的箱子里凑成整箱.这样保证移动了最少的瓶数
如果考虑不同仓库,就像你说的,需要先把每个仓库能凑整的凑整,这样N个仓库就会剩下0~N个不整的箱子,将他们无差别(也可能有差别,因为仓库间距离不同,同仓库就不考虑各个箱子间的距离差别了)操作一次,

"""
    1.大到小排序
    2.移动最少原则,将当前水最少的箱拆散填补到最多的箱子中
    3.结果为N个满箱M[0~1]个不满的
"""
FULL = 24

def describe(frm, to, amount, cur):
    print("从{}拿出{}个放到{},目前有{}个".format(frm, amount, to, cur))


def Do(_boxes):
    boxes = _boxes.copy()  # 复制数据避免修改原数据
    boxes.sort(key=lambda x: x["amount"], reverse=True)
    tail = len(boxes) - 1

    for index in range(len(boxes)):
        amount = boxes[index]["amount"]
        name = boxes[index]["name"]
        if amount == 0:
            # 循环到空箱,后边必然全空,前边必然全满,结束
            break
        if index == tail:
            # 首尾相遇,操作完毕
            break
        while FULL - amount > 0 and index != tail:
            # 当前箱不满,将尾部箱拆散
            tail_amount = boxes[tail]["amount"]
            if tail_amount > (FULL-amount):
                # 尾部比缺的多,拿出一部分填满,跳出
                boxes[tail]["amount"] -= (FULL-amount)
                boxes[index]["amount"] = FULL
                describe(boxes[tail]["name"], name, FULL-amount, FULL)
                break
            else:
                # 不多,那么拿空尾部,去掉尾部箱,继续判断是否仍要处理下一个
                boxes[index]["amount"] += tail_amount
                boxes[tail]["amount"] = 0
                describe(boxes[tail]["name"], name,
                         tail_amount, boxes[index]["amount"])
                tail -= 1
    return boxes


wh1 = [{"name": "a1",
        "amount": 21},
       {"name": "a2",
        "amount": 15},
       {"name": "a3",
        "amount": 13}]
wh2 = [{"name": "b1",
        "amount": 4},
       {"name": "b2",
        "amount": 8},
       {"name": "b3",
        "amount": 23}]
wh3 = [{"name": "c1",
        "amount": 11}]

wh1 = Do(wh1)
wh2 = Do(wh2)
wh3 = Do(wh3)
rest = []
for wh in (wh1, wh2, wh3):
    for i in wh:
        if i["amount"] < FULL and i["amount"] > 0:
            rest.append(i)
Do(rest)
//从a3拿出3个放到a1,目前有24个
//从a3拿出9个放到a2,目前有24个
//从b1拿出1个放到b3,目前有24个
//从b1拿出3个放到b2,目前有11个
//从a3拿出1个放到b2,目前有12个
//从c1拿出11个放到b2,目前有23个

后边和你你描述的有点出入,因为你是在进行顺序操作了,将A没处理完的带到了B中成了B4,我这个是全部处理完再处理剩余的,这个算法依然比较简单,不过效率是O(N)的,空间复杂度也是O(N),我就当做题了