首页 文章

再分配算法

提问于
浏览 次
7

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

我需要对球进行重新分配，因此每个球桶由红球的59-61％球重和蓝球的39-41％球重组成 . 每个铲斗应具有与重新分配之前完全相同的重量，但每个铲斗中的球数不必与之前的数量相匹配 . 分割球是可能的，但每次分割都有成本 .

有人能指出我的算法方向吗？

谢谢 .

algorithm sorting

1 回答

  • 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) )
    回复于

相关问题