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

Question

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

我有一个包含各种项目的"容器"列表。容器中包含的每个项目都有数量和类型，因此可能一个容器有 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 个桃子(或者可能所有 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

Answer 2

这个问题可以通过查看每个容器并决定是否包含(获取)容器i来解决。

因此，我们一个接一个地遍历所有容器，对于每个容器，我们都会选择2个选项： 1.包括容器 2. 排除容器

我们以递归方式执行此调用。在每次调用时，如果我们包含容器，我们需要递增 #of 容器。同时减少剩余项目 #of。

我们一直这样做，直到我们达到没有容器留下的情况，或者我们已经满足了所需的所有物品。 然后，我们取所有看到的值的最小值。