时间戳

首页 > 解决方案 > 关于如何将尽可能多的列表放入不同容量的桶中的算法

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

问题描述

我试图找出一种算法，将尽可能多的数字放入不同容量的存储桶列表中。它旨在解决一个问题，即一组跑不同英里的跑步者在不跳过一条腿的情况下完成尽可能多的拉格纳接力腿。

下面的 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]

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

给定一条起始腿（在本例中为 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}

标签： pythonalgorithmoptimizationbacktracking

解决方案

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

 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)

我只是在这里转录了数学模型。

推荐阅读