excel - 在每个 jar 中找到最大容量的最小 jar 数，以容纳最大数量的葡萄酒

我的业务是葡萄酒转售业务，我们有这个问题，我一直在努力解决。我们有50-70种葡萄酒可随时储存，约500个不同容量的罐。每罐只能装一种酒我的工作是确定最小数量的罐，以保持最大数量的类型的葡萄酒，每一个尽可能接近其最大容量，即100L的葡萄酒不应该被储存在一个200升的罐中，如果有2个60L和40L的罐也存在。
我一直在用excel手工完成这项工作，并想尝试自动化这个过程，但是使用宏和数组公式很快就失控了。我可以用C和Swift编写一个简单的程序，但一直在寻找通用算法我很感激你能告诉我从哪里开始一个完整的解决方案，我会送你一瓶；）
编辑：为了澄清，我知道我有多少种葡萄酒，以及它们的总量，例如700升的皮诺葡萄酒，2000升的梅洛葡萄酒等等。这些都是每周变化的。但是，这些罐有许多不同的容量（40、60、80、100、200升等），由于必须取出清洗和更换，因此更换的间隔不规则。仅仅用70个坦克装70种是不可能的。
而且，葡萄酒的总数量与总罐的容量不匹配，我需要使用最小数量的罐来保存最大数量的葡萄酒。如果容量不足，剩下的葡萄酒必须尽可能少（它们会很快变质）。如果有剩余，每种类型的剩余量必须与其数量成比例。
一个简单的例子是：

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和坦克容量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和梅洛的355l，使存储量与我们拥有的量成比例。
很明显这是不可能的，因为你不能混合葡萄酒，但我们应该能够接近。
要储存比诺，最接近的方法是使用1 (40l)和3 (80l)，然后用剩下的来储存梅洛。
这可以实现为一个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]]

计算比例，然后对每种类型的葡萄酒运行此操作（移除已选择的罐，可以使用d数组找到这些罐，如果需要，我可以详细说明）。环顾四周，找出每种葡萄酒可能达到的最接近的总和。
这对于几百辆坦克来说应该足够快了，我猜容量不会超过几千辆。

关于excel - 在每个 jar 中找到最大容量的最小 jar 数，以容纳最大数量的葡萄酒，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31516359/