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

Question

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

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

我必须想出一个算法来接收此信息和请求，并返回可以满足此类请求的最小容器数。该请求本质上是一个包含想要的元素及其数量的列表，可以将其视为购物 list 。

所以根据我上面给出的例子:

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 个桃子(或者可能所有 6 个桃子都是从 B 和 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

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

此外，我认为它不能很好地处理边缘情况。例如:假设可用容器无法满足请求。该算法将挑选所有容器而实际上并没有取得任何成果，只是因为优先级会给它们一个非零分数。

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

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

Answer 1

首先，您的解决方案还有另一个问题，而不是优化不当/处理不当的情况。

例如，对于这个测试用例:

Container A:
    10 apples
Container B:
    5 apples
    1 pear
Container C:
    5 apples
    1 pear
Request:
    10 apples
    2 pears

您的代码将返回 3 个容器(容器 A 在第 1 次迭代时得分最高)。

有一种简单的方法可以给出正确的结果但具有指数级的复杂性:

resultContainers = None
resultNumberContainers = inf
for each binary_mask in range(0, pow(2,containerLength)):
    actContainer = emptyContainer
    numberContainers = 0
    for each i in range(0,containerLength):
        if(pow(2,i) & binary_mask):
            actContainer = actContainer + containers[i]
            numberContainers += 1
    if(ok(actContainer) && numberContainers < resultNumberContainers):
        resultNumberContainers = numberContainers
        resultContainers = actContainer