ortools系列：装箱问题
ortools系列：装箱问题
1. Bin Packing
装箱问题的简化版本就是背包问题，背包问题是学习动态规划的一道简单又复杂的问题。在实际工作中，简单背包问题实用场景不多，但是如果把问题简化不需要那么精确的解法，背包问题又是很通用的模型。
在ortools的文档中，只有简单背包问题的案例，实际中，三维装箱问题更为常见更为实用。在ortools的论坛中也有人提出这个问题，但是讨论并不到，这个问题要归到约束规划中。
我们还是看代码吧。
from ortools.algorithms import pywrapknapsack_solver
def main():
# Create the solver.
# 调用背包动态规划求解器，这是一个背包问题的专门解决方法
#
solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
test)
values = [360, 83, 59, 130, 431, 67, 230, 52, 93,
125, 670, 892, 600, 38, 48, 147, 78, 256,
63, 17, 120, 164, 432, 35, 92, 110, 22,
42, 50, 323, 514, 28, 87, 73, 78, 15,
26, 78, 210, 36, 85, 189, 274, 43, 33,
10, 19, 389, 276, 312]
weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70,
64, 59, 18, 0, 36, 3, 8, 15, 42,
9, 0, 42, 47, 52, 32, 26, 48, 55,
6, 29, 84, 2, 4, 18, 56, 7, 29,
93, 44, 71, 3, 86, 66, 31, 65, 0,
79, 20, 65, 52, 13]]
capacities = [850]
solver.Init(values, weights, capacities)
computed_value = solver.Solve()
packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]
total_weight = sum(packed_weights)
print("Packed items: ", packed_items)
print("Packed weights: ", packed_weights)
print("Total value: ", computed_value)
print("Total weight: ", total_weight)
if __name__ == __main__:
main()
# 结果
Packed items: [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30, 31, 32, 34, 38, 39, 41, 42, 44, 47, 48, 49]
Packed weights: [7, 0, 22, 80, 11, 59, 18, 0, 3, 8, 15, 42, 9, 0, 47, 52, 26, 6, 29, 84, 2, 4, 18, 7, 71, 3, 66, 31, 0, 65, 52, 13]
Total value: 7534
Total weight: 850
上面的例子演示了一个简单背包问题，每件物品有一定的体积和重量，如何装载物品才能最大化利用背包的空间。这个问题也可以建模成整数规划问题，只不过用背包的动态规划方法速度回快得多。
以后有时间再补充三维装箱问题吧。
2. 参考
- google_ortools_guide
大家看完记得关注点赞.
master苏.
推荐阅读：