需要在加权桶之间按比例分配值的算法

Question

似乎我遇到了类似 Algorithm for constrained proportional distribution 的问题，但我无法针对我的任务扩展解决方案。

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

我的算法是：

我们获取只能分配给 1 个桶的值并分配它们。计算比例。（5000 为 30000（16%），8000 为 17000（47%），11000 为 60000（18%））

2.1。取可以分配给 2 个桶的值。在第 1 步之后使用这两个最小分配的桶。尝试用部分值填充它，以便它与第二个桶具有相同的比例。值3000可以分配给30000和17000。此时30000有16%，17000有47%，所以我们试着把3000放到30000上，它会有(5000+3000)/30000 = 26%的分配。还是不到47%，还可以。如果超过 47%，我们将填充到 47%，并在 30000 和 17000 之间按比例平均分配超出部分。

2.2。拿另一对水桶。等等。直到我们分发所有 2 桶值。

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

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

要检查的数据：
,0,1,2,3,4,5
0,0,9000,9000,4500,4500,1000
1,1000,1,1,1,1,0
2,1000,1,1,1,1,0
3,1000,1,1,1,1,0
4,1000,1,1,1,1,0
5,1000,1,1,1,1,0
6,1000,1,1,1,1,0
7,1000,1,1,1,1,0
8,1000,1,1,1,1,0
9,1000,1,1,1,1,0
10,1000,0,0,0,0,1
并期望得到结果：
0.33,0.33,0.17,0.17
,0,1,2,3,4,5
0,0,9000,9000,4500,4500,1000
1,1000,0.33,0.33,0.17,0.17,0
2,1000,0.33,0.33,0.17,0.17,0
3,1000,0.33,0.33,0.17,0.17,0
4,1000,0.33,0.33,0.17,0.17,0
5,1000,0.33,0.33,0.17,0.17,0
6,1000,0.33,0.33,0.17,0.17,0
7,1000,0.33,0.33,0.17,0.17,0
8,1000,0.33,0.33,0.17,0.17,0
9,1000,0.33,0.33,0.17,0.17,0
10,1000,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]])

需要在加权桶之间按比例分配值的算法

Need algorithm for proportional value distributions between weighted buckets

algorithm

math

bucket