我有一千个不同大小的桶。每个桶由不同重量的红色和蓝色球组成。我知道球总重量的 60% 来自红球，40% 来自蓝球。每个桶有随机数量的球，随机分布的红球和蓝球，以及随机分布的球重量。
我需要重新分配球，使每个桶中 59-61% 的球重量来自红球，39-41% 的球重量来自蓝球。每个桶的重量应该与重新分配前的重量完全相同，但每个桶中球的数量不必与之前的数量一致。可以拆分球，但每次拆分都有成本。
谁能指出算法的方向？
谢谢。
最佳答案
一种可能的方法是按以下方式制定混合整数规划问题。我不确定，可能还有其他更有效的解决方案。
假设共有 R 个红球和 B 个蓝球，每个球的重量分别为 r1, r2, ..rR 和 b1, b2, ...bB。
假设 Rij 是分配给桶 j 的红球 i 的分数。 RBINij 是一个二进制数，如果 Rij > 0 则为 1，否则为 0。我们希望尽可能多地生成 Rij 的 0(和 RBINij 的 0)以实现最少的切割次数。
类似地，Bij 是分配给桶 j 的蓝色球 i 的分数。 BBINij 是一个二进制数，如果 Bij > 0 则为 1，否则为 0。我们希望尽可能多地生成 Bij 的 0(和 BBINij 的 0)以实现最少的切割次数。
Constraints:
summation over i( wi*Rij ) <= 1.564*summation over i( wi*Bij ) (61-39 ratio) { for all j buckets }
summation over i( wi*Rij ) >= 1.439*summation over i( wi*Bij ) (59-41 ratio) { for all j buckets }
RBINij >= Rij
BBINij >= Bij
+ maybe more constraints like the total weight etc.
Objective Function:
Minimize( Ci*summation over i(RBINij + BBINij) )
关于algorithm - 再分配算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19115835/