algorithm - 找到覆盖项目列表所需的最小容器数的算法

问题描述

我有一个不特定于任何语言或框架的问题，它更像是一个算法问题：

我有一个包含各种项目的“容器”列表。容器中包含的每个物品都有数量和类型，因此可能一个容器有 3 个苹果和 2 个桃子，另一个容器有 12 个桃子，另一个容器有 5 个梨。

我必须想出一个算法来接收这些信息和一个请求，并返回可以满足此类请求的最小容器数。请求本质上是一份想要的物品清单以及他们想要的数量，把它想象成一个购物清单。

所以基于我上面给出的例子：

Container A:
    3 x apple
    2 x peach

Container B:
    12 x peach

Container C:
    5 x pear

和这个要求

I want:
    1 x apple
    6 x peach

算法应该告诉我，满足这个请求的最佳方法是同时使用容器 A 和 B，并且将从 A 消耗 1 个苹果和 2 个桃子，从 B 消耗 4 个桃子（或者可能从 B 消耗所有 6 个桃子而A只用于苹果，真的没关系）。

此外，该算法应该能够根据可用容器判断何时无法满足请求（例如：无法满足 35 个西瓜的请求），并在可能的情况下为不同的容器赋予不同的优先级（例如：与其他内容非常相似但更难快速交付给客户的容器相比，交付速度更快的容器应该会得到提升）。

到目前为止，我已经尝试过使用一种非常琐碎且有点蹩脚的评分算法（伪代码）：

itemsLeft = copy(itemsInRequest)
containersLeft = copy(containers)
choosenContainers = []

while len(itemsLeft) > 0:
    if len(containersLeft) == 0:
        return Error("No more containers, can't satisfy request")
    bestScore = 0
    bestContainer = null
    foreach container in containersLeft:
        // Give a score based on the items it contains
        score = 0
        foreach item in itemsLeft:
            if container.contains(item.type):
                score += min(container.quantityOf(item.type), item.wantedQty)
        // Take priority into account
        score += container.priority
        if score > bestScore:
            bestScore = score
            bestContainer = container
    choosenContainers.append(bestContainer)
    containersLeft.remove(bestContainer)
    foreach item in itemsLeft:
        if bestContainer.contains(item.type):
            quantityInContainer = bestContainer.quantityOf(item.type)
            // This will consume items in itemsLeft, eventually
            // removing them from the list if the quantity
            // reaches 0
            item.consume(quantityInContainer)
return choosenContainers

但我对它不是很满意，因为我不认为它是经过深思熟虑和性能好的，但我现在想不出更好的东西。

另外我认为它不能很好地处理边缘情况。例如：想象一个请求不能用可用的容器来满足。该算法将挑选所有容器而没有真正实现任何目标，只是因为优先级会给它们一个非零分数。

我在想，也许这样的事情可以通过一些我不知道的已经存在的、经过实战验证的算法来实现？

您能否推荐任何解决此类问题或类似问题的算法，以便我可以从中获得灵感，或者就您将如何解决这个问题提出一些建议？

标签： algorithmoptimization

algorithm - 找到覆盖项目列表所需的最小容器数的算法

问题描述

解决方案

推荐阅读