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蘇.
推薦閱讀：