关于如何将尽可能多的列表放入不同容量的桶中的算法

Question

我正在尝试找出一种算法，将尽可能多的数字放入不同容量的桶列表中。它旨在解决一个问题，即一群运行的运行不同英里的人跑完尽可能多的 Ragnar 接力赛段而不跳过一段赛段。

下面的 36 个数字（以英里为单位的航段）可以重复多次，并且可以从列表中的任何航段开始。

legs = [3.3, 4.2, 5.2, 3, 2.7, 4, 
    5.3, 4.5, 3, 5.8, 3.3, 4.9, 
    3.1, 3.2, 4, 3.5, 4.9, 2.3, 
    3.2, 4.6, 4.5, 4, 5.3, 5.9, 
    2.8, 1.9, 2.1, 3, 2.5, 5.6, 
    1.3, 4.6, 1.5, 1.2, 4.1, 8.1]

运行的列表：

runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]

如果我们认为腿是数字列表而运行s 是桶，那么尝试将尽可能多的数字放入不同容量的桶就变成了一个优化问题。

给定一条起始腿（在本例中为 1），找出可以覆盖多少条腿。以下是从支路 1 开始的示例输出：

Total run mileage = 32.0
Total legs covered = 7 (L1, L2, L3, L4, L5, L6, L7) Total mileage used = 27.7
Total mileage wasted = 4.3
{'Total': 3.2, 'Reminder': 0.2, 'Index': 0, 'L4': 3}
{'Total': 12.3, 'Reminder': 0.8, 'Index': 1, 'L1': 3.3, 'L2': 4.2, 'L6': 4}
{'Total': 5.2, 'Reminder': 0.0, 'Index': 2, 'L3': 5.2}
{'Total': 2.9, 'Reminder': 0.2, 'Index': 3, 'L5': 2.7}
{'Total': 2.9, 'Reminder': 2.9, 'Index': 4}
{'Total': 5.5, 'Reminder': 0.2, 'Index': 5, 'L7': 5.3}

Answer 1

我认为这可以作为一个显式优化问题（准确地说是一个整数规划模型）来编写和解决：

 Input data: 
      L[i], r[j] (legs and runs)

 Binary variables 
      assign[i,j] (runner j does leg i) 
      covered[i]  (leg i is covered by a runner) 

 Model:

    max sum(i, covered[i])                 (objective)
        sum(i,L[i]*assign[i,j]) <= r[j]    (runner capacity)
        covered[i] <= sum(j,assign[i,j])   (leg is covered)
        covered[i] <= covered[i-1]         (ordering of legs)

这不是代码而是数学模型。代码将取决于所使用的 MIP 求解器（和建模工具）。当解决这个模型时，我得到：

----     52 PARAMETER report  results

              run1        run2        run3        run4        run5        run6

leg1                     3.300
leg2                     4.200
leg3                                 5.200
leg4         3.000
leg5                                             2.700
leg6                     4.000
leg7                                                                     5.300
total        3.000      11.500       5.200       2.700                   5.300
runLen       3.200      12.300       5.200       2.900       2.900       5.500

注：我这里基本都是打印出来的assign[i,j]*covered[j]*L[i]。原因是某些变量assign[i,j]可能被打开，而相应的covered[j]=0。所以只打印 assign 可能有点误导。

使用 cvxpy 的示例实现如下所示：

import cvxpy as cp

legs = [3.3, 4.2, 5.2, 3, 2.7, 4, 
    5.3, 4.5, 3, 5.8, 3.3, 4.9, 
    3.1, 3.2, 4, 3.5, 4.9, 2.3, 
    3.2, 4.6, 4.5, 4, 5.3, 5.9, 
    2.8, 1.9, 2.1, 3, 2.5, 5.6, 
    1.3, 4.6, 1.5, 1.2, 4.1, 8.1]

runs = [3.2, 12.3, 5.2, 2.9, 2.9, 5.5]

n = len(legs)  
m = len(runs) 

assign = cp.Variable((n,m),boolean=True)
covered = cp.Variable(n,boolean=True)

prob = cp.Problem(cp.Maximize(cp.sum(covered)),
                  [
                   assign.T@legs <= runs,
                   covered <= cp.sum(assign,axis=1),
                   covered[1:n]<=covered[0:(n-1)]
                  ])

prob.solve()

# reporting of solution 
L = round(prob.value)  
result = assign.value[0:L,]
for i in range(L):
  for j in range(m):
    result[i,j] *= covered.value[i]*legs[i] 
print(result)

我只是把数学模型抄录在这里

关于如何将尽可能多的列表放入不同容量的桶中的算法

algorithm on how to put as many numbers of a list into different capacity of buckets

python

algorithm

optimization

backtracking