我的业务是 Wine 转售业务，我一直在努力解决这个问题。我们有50-70种 Wine 可以随时储存，大约500个不同容量的 jar 。每个 jar 只能装一种酒。我的工作是确定最少数量的 jar 来容纳最多数量的 Wine ，每个 jar 都尽可能接近其最大容量，即如果有 2 个 60 升和 40 升的 jar ，则不应将 100 升的 Wine 储存在 200 升的 jar 中也存在。
我一直在 excel 中手工完成这项工作，并想尝试自动化该过程，但使用宏和数组公式很快就会失控。我可以用 C 和 Swift 编写一个简单的程序，但一直在寻找通用算法。非常感谢您指出我可以从哪里开始。一个完整的解决方案，我会寄给你一瓶 ;)
编辑:澄清一下，我确实知道我有多少种 Wine 及其总量，即 700 升的皮诺、2000 升的梅洛等。这些每周都会变化。然而，这些水箱有许多不同的容量(40、60、80、100、200 升等)并且不定期更换，因为它们必须被取出进行清洁和更换。简单地用70个坦克来容纳70种是不可能的。
此外，酒的总量永远不会与 jar 的总容量相匹配，我需要使用最少数量的 jar 来容纳最大量的酒。如果容量不足，剩余的酒量必须尽可能少(它们会很快变质)。如果有剩余，则每种类型的剩余量必须与其数量成正比。
这个问题的一个简化示例是这样的:
Wine:
----------
Merlot 100
Pinot 120
Tocai 230
Chardonay 400
Total: 850L
Tanks:
----------
T1 10
T2 20
T3 60
T4 150
T5 80
T6 80
T7 90
T8 80
T9 50
T10 110
T11 50
T12 50
Total: 830L
最佳答案
此贪心 DP 算法尝试执行比例拆分:例如，如果您有 700l Pinot、2000l Merlot 和 jar 容量 40、60、80、100、200，即总容量为480。
700 / (700 + 2000) = 0.26
2000 / (700 + 2000) = 0.74
0.26 * 480 = 125
0.74 * 480 = 355
因此，我们将尝试存储 125l 的 Pinot 和 355l 的 Merlot，以使存储量与我们拥有的数量成正比。
显然这不是完全可能的，因为你不能混合 Wine ，但我们应该能够接近。
要储存 Pinot，最接近的是使用 jar 1 (40l) 和 3 (80l)，然后将其余的用于 Merlot。
这可以实现为 subset sum问题:
d[i] = true if we can make sum i and false otherwise
d[0] = true, false otherwise
sum_of_tanks = 0
for each tank i:
sum_of_tanks += tank_capacities[i]
for s = sum_of_tanks down to tank_capacities[i]
d[s] = d[s] OR d[s - tank_capacities[i]]
计算比例，然后针对您拥有的每种 Wine 运行此程序(移除已经选择的 jar ，您可以使用 d 数组找到它们，如果需要，我可以详细说明)。环顾 d[computed_proportion] 以找到每种 Wine 类型可能达到的最接近的总和。
这对于几百个坦克来说应该足够快了，我猜它的容量不会超过几千个。
关于excel - 在每个 jar 的最大可能容量下，找到容纳最大数量 Wine 的最少 jar 数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31516359/