algorithm - 再分配算法

Question

我有一千个大小不一的桶。每个桶由不同重量的红色和蓝色球组成。我知道球总重量的 60% 来自红球，40% 来自蓝球。每个桶有随机数量的球，随机分布的红色和蓝色球，以及随机分布的球权重。

我需要重新分配球，所以每个桶由 59-61% 的红球重量和 39-41% 的蓝球重量组成。每个桶的重量应该与重新分配之前完全相同，但每个桶中的球数不必与之前的数字相匹配。可以拆分球，但每次拆分都有成本。

谁能指出我的算法方向？

谢谢。

Answer 1

一种可能的方法是按以下方式制定混合整数规划问题。我不确定，可能还有其他更有效的解决方案。

假设总共有 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) )