在每个水箱的最大可能容量上查找保存最大数量的葡萄酒的最less数量的水箱
我的业务是在葡萄酒转售业务，我们有这个问题，我一直在努力解决。 我们随时可以储存50-70种葡萄酒，大约500个不同容量的葡萄酒jar。 每个jar子只能装一种酒。 我的工作是确定最less数量的葡萄酒，每个葡萄酒的种类尽可能接近其最大容量，也就是说，如果两个容量为60升和40升的葡萄酒不应该储存在200升的容器中也存在。
我一直在excel中手工完成这个工作，并想尝试自动化这个过程，但是使用macros和数组公式会很快失控。 我可以在C和Swift中编写一个简单的程序，但坚持find一个通用的algorithm。 而我可以开始的指针非常感谢。 一个完整的解决scheme，我会给你一瓶;）
编辑：澄清，我知道我有多less种types的葡萄酒和他们的总量，即黑比诺700l，美乐2000l等，这些变化每周。 然而，这些油箱有许多不同的容量（40,60,80,100,200升等），并且以不规则的间隔变化，因为它们必须被取出以进行清洁和更换。 简单地使用70个坦克来保存70种types是不可能的。
此外，总量的葡萄酒从来没有匹配坦克的总容量，我需要使用最less数量的坦克来保持最大量的葡萄酒。 在容量不足的情况下，留下的酒量必须尽可能小（它们很快就会变质）。 如果剩余，每种types剩余的数量必须与其数量成比例。
这个问题的简单例子是：
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 这种贪婪-DPalgorithm尝试执行比例分割：例如，如果您有700l Pinot, 2000l Merlot和jar容量700l Pinot, 2000l Merlot ，这意味着总容量为480 。
700 / (700 + 2000) = 0.26 2000 / (700 + 2000) = 0.74 0.26 * 480 = 125 0.74 * 480 = 355
所以我们将尝试储存美355l和355l ，以使存储量与我们的量成正比。
显然这是不完全可能的，因为你不能混合葡萄酒，但我们应该能够足够接近。
要储存比诺，最接近的将是使用坦克1 (40l) 3 (80l)和3 (80l) ，然后用其余的梅洛。
这可以作为一个子集和问题来实现：
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]]
计算比例，然后对每种葡萄酒运行这个比例（移除已经select的坦克，你可以使用d数组find它，我可以详细说明是否需要）。 查看d[computed_proportion]查找每种葡萄酒types可能达到的最接近的总和。
这应该是足够快的几百坦克，我猜测没有能力超过几千。