需要加权桶之间的比例值分布算法

Question

似乎我有类似约束比例分布算法的问题，但我无法将解决方案扩展到我的任务。

假设我们有X个加权桶(例如30000、17000、60000(和值Y(例如2000、3000、5000、8000、9000、11000(。在矩阵中，所有值都被标记为是否可以分配到bucket(1-允许，0-不允许(。我们需要将价值分配到桶中，以便比例尽可能相等。在这种情况下，我们将为30000个桶(33%(分配10000个，为17000个桶(47%(分配8000个，为60000个桶分配20000个(33%(。

我的算法是：

1. 我们获取只能分配给1个bucket的值并进行分配。计算比例。(30000人中有5000人(16%(，17000人中有8000人(47%(，60000人中有11000人(18%((

2.1。取可分配给2个存储桶的值。在第1步之后，取最小分配为这两个的bucket。试着用零件值填充它，这样它将具有与第二个桶相同的比例。值3000可以分配给30000和17000。目前，30000有16%，17000有47%，所以我们试着把3000到30000，它将有(5000+3000(/300000=26%的分配。仍然低于47%，没关系。如果超过47%，我们将填补47%，并按比例将超额部分平均分配在30000至17000之间。

2.2.再拿一对水桶。依此类推。直到我们将分发所有的2-bucket值。

3. 取可分配给3个存储桶的值。检查最小比例，将其填充到下一个。在用多余的值将它们平均填充到第三个之后。继续，直到所有值都将被分发

我觉得我们可以得到这样的情况，即分布顺序(例如3000->2000或2000->3000(可以给我们不同的结果。因此，我们需要采取其他措施来避免这种情况。在这个任务中，我们没有任何约束，我们只希望在最后达到相等的比例(或尽可能接近(。这项任务的理论有什么帮助吗？或者可以是另一种算法。

要检查的数据：
，0,1,2,3,4,5
0,090009000450045001000
111000,1,1,1,1,0
21000,1,1,10,1,0
41000,1,1,1,0
51000,1,1,11,1,0
61000,1,1,11,1,0
17100,1,1,10,0
81000,1,1,1,10,10,1,0
91000,1,1,1-1,0
1101000,0,0,0,00,1
并期望得到结果：
0.33,0.33,0.17,0.17
，0,1,2,3,4,5
0,09000450045001000
11000,0.33,0.33,0.17,017,0
21000,0.33,0.17,17,0.17,0
31000,0.33,00.33,0.17,0.17,0.17,0
41000,0.33,0.3,0.33,00.17,0
51000,0.33,03.3,0.17,0.17,0
161000,0.33,0.03,0.33,01.77,0.17,0
7100,0.33,0.30,0.33,0.17,.17,0
91000,0.33,0.32,0.17,0
1101000,0 0,0,0,1
所以我们会有一个铲斗装满100%(1000个铲斗(，4个铲斗平均装满33%。

请检查下面的算法。

Matrix example
<table>
<tr>
<th>value</th>
<th>30000</th>
<th>17000</th>
<th>60000</th>
</tr>
<tr>
<th>2000</th>
<th>0</th>
<th>1</th>
<th>1</th>
</tr>
<tr>
<th>3000</th>
<th>1</th>
<th>1</th>
<th>0</th>
</tr>
<tr>
<th>5000</th>
<th>1</th>
<th>0</th>
<th>0</th>
</tr>
<tr>
<th>8000</th>
<th>0</th>
<th>1</th>
<th>0</th>
</tr>
<tr>
<th>9000</th>
<th>1</th>
<th>1</th>
<th>1</th>
</tr>
<tr>
<th>11000</th>
<th>0</th>
<th>0</th>
<th>1</th>
</tr>
</table>

Answer 1

以下代码位于Python 3中，使用OR Tools库。

# reads the CSV export of the .xlsx files, writes CSV to stdout
import csv
import fileinput
import sys
from ortools.linear_solver import pywraplp
# read the input
rows = list(csv.reader(fileinput.input()))
values = [float(row[1]) for row in rows[2:-1]]
buckets = [float(cell) for cell in rows[1][2:-1]]
eligible_member = [[int(cell) for cell in row[2:-1]] for row in rows[2:-1]]
# the solver must have good symmetry breaking, else this formulation is bad
solver = pywraplp.Solver.CreateSolver("solver", "SCIP")
# minimize the max fill ratio minus the min fill ratio
max_fill_ratio = solver.NumVar(0, solver.infinity(), "")
min_fill_ratio = solver.NumVar(0, solver.infinity(), "")
solver.Objective().SetMinimization()
solver.Objective().SetCoefficient(max_fill_ratio, 1)
solver.Objective().SetCoefficient(min_fill_ratio, -1)
# fractional indicator variables -- indicators[i][j] is the fraction of value i
# assigned to bucket j
indicators = [[solver.NumVar(0, cell, "") for cell in row] for row in eligible_member]
# ensure that each value is exactly 100% assigned
for i, value in enumerate(values):
exact_cover_constraint = solver.Constraint(1, 1)
for j, bucket in enumerate(buckets):
exact_cover_constraint.SetCoefficient(indicators[i][j], 1)
# the usual trick for minimizing a maximum -- constrain it to be greater than or
# equal to each value maximized over, let the solver do the rest
for j, bucket in enumerate(buckets):
max_load_constraint = solver.Constraint(-solver.infinity(), 0)
max_load_constraint.SetCoefficient(max_fill_ratio, -1)
min_load_constraint = solver.Constraint(0, solver.infinity())
min_load_constraint.SetCoefficient(min_fill_ratio, -1)
for i, value in enumerate(values):
ratio = value / bucket
max_load_constraint.SetCoefficient(indicators[i][j], ratio)
min_load_constraint.SetCoefficient(indicators[i][j], ratio)
# enable to diagnose slowness
if False:
solver.EnableOutput()
if solver.Solve() != solver.OPTIMAL:
raise RuntimeError
w = csv.writer(sys.stdout)
w.writerow([solver.Objective().Value()] + buckets)
for i, value in enumerate(values):
w.writerow([value] + [indicator.solution_value() for indicator in indicators[i]])