OR-Tools 解决的问题类型：
Linear optimizationConstraint optimizationMixed-integer optimizationBin packingNetwork flowsAssignmentSchedulingRouting包装问题：
包装一组给定大小的项目到容器与固定容量。典型的应用是有效地将箱子装到送货卡车上。通常，由于容量限制，无法打包所有项目。在这种情况下，问题是查找最大总大小的项的子集，该子集将适合容器。两个最重要的是背包问题和垃圾箱包装。
背包问题：在简单的背包问题中，有一个容器（背包）。项目具有值和大小，目标是最大化包装物料的总大小。
例如：50 个项目被打包到一个垃圾箱中。每个项目都有一个值（物料上的数字）和一个权重（大致与物料的面积成正比）。被声明为容量为 850，我们的目标是找到一组项目，这些项将最大化不超出容量的总成本。
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] from __future__ import print_function from ortools.algorithms import pywrapknapsack_solver def main(): # Create the solver. solver = pywrapknapsack_solver.KnapsackSolver( pywrapknapsack_solver.KnapsackSolver. KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackExample') 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 = [] packed_weights = [] total_weight = 0 print('Total value =', computed_value) for i in range(len(values)): if solver.BestSolutionContains(i): packed_items.append(i) packed_weights.append(weights[0][i]) total_weight += weights[0][i] print('Total weight:', total_weight) print('Packed items:', packed_items) print('Packed_weights:', packed_weights) if __name__ == '__main__': main()也有更一般版本的背包问题。下面是几个示例：
多维背包问题，其中项目具有多个物理数量，如重量和体积，背包具有每个数量的容量。在这里，术语维度不一定指高度、长度和宽度的常用空间维度。但是，有些问题可能涉及空间维度，例如，找到将矩形框打包到矩形存储箱中的最佳方法。
多个背包问题，其中有多个背包，目标是最大化所有背包中包装物品的总成本。
请注意，单个背包可以出现多维问题，或者只有一个维度的多背包问题。
通常将容器称为箱，而不是背包。从不同权重和值的项的集合开始。问题是将项目的子集打包到五个 bin 中，每个条柱的最大容量为 100，以便总包装值为最大值。每个变量都是 0-1 变量，每个项目最多可以放在一个 bin 中，包装在每个箱中的总重量不能超过其容量。
from __future__ import print_function from ortools.linear_solver import pywraplp def create_data_model(): """Create the data for the example.""" data = {} weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36] values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25] data['weights'] = weights data['values'] = values data['items'] = list(range(len(weights))) data['num_items'] = len(weights) num_bins = 5 data['bins'] = list(range(num_bins)) data['bin_capacities'] = [100, 100, 100, 100, 100] return data def main(): data = create_data_model() # Create the mip solver with the CBC backend. solver = pywraplp.Solver.CreateSolver('multiple_knapsack_mip', 'CBC') # Variables # x[i, j] = 1 if item i is packed in bin j. x = {} for i in data['items']: for j in data['bins']: x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j)) # Constraints # Each item can be in at most one bin. for i in data['items']: solver.Add(sum(x[i, j] for j in data['bins']) <= 1) # The amount packed in each bin cannot exceed its capacity. for j in data['bins']: solver.Add( sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= data['bin_capacities'][j]) # Objective objective = solver.Objective() for i in data['items']: for j in data['bins']: objective.SetCoefficient(x[(i, j)], data['values'][i]) objective.SetMaximization() status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print('Total packed value:', objective.Value()) total_weight = 0 for j in data['bins']: bin_weight = 0 bin_value = 0 print('Bin ', j, '\n') for i in data['items']: if x[i, j].solution_value() > 0: print('Item', i, '- weight:', data['weights'][i], ' value:', data['values'][i]) bin_weight += data['weights'][i] bin_value += data['values'][i] print('Packed bin weight:', bin_weight) print('Packed bin value:', bin_value) print() total_weight += bin_weight print('Total packed weight:', total_weight) else: print('The problem does not have an optimal solution.') if __name__ == '__main__': main() Total packed value: 395.0 Bin 0 Item 2 - weight: 42 value: 25 Item 8 - weight: 36 value: 30 Packed bin weight: 78 Packed bin value: 55 Bin 1 Item 4 - weight: 36 value: 35 Item 12 - weight: 42 value: 20 Packed bin weight: 78 Packed bin value: 55 Bin 2 Item 1 - weight: 30 value: 30 Item 3 - weight: 36 value: 50 Item 10 - weight: 30 value: 45 Packed bin weight: 96 Packed bin value: 125 Bin 3 Item 5 - weight: 48 value: 30 Item 7 - weight: 42 value: 40 Packed bin weight: 90 Packed bin value: 70 Bin 4 Item 9 - weight: 24 value: 35 Item 13 - weight: 36 value: 30 Item 14 - weight: 36 value: 25 Packed bin weight: 96 Packed bin value: 90 Total packed weight: 438箱装包装问题也涉及将物品装入箱中。但是，箱装问题有不同的目标：找到容纳所有物料的箱子数量很少。
其中一个最有名的包装问题是箱装，其中有多个容器（称为箱）的容量相等。与多个背包问题不同，条柱的数量不是固定的。相反，目标是查找将容纳所有项的最小数量的 bin。
下面是一个简单的示例，用于说明多个背包问题与箱装问题的区别。假设一家公司有送货卡车，每辆都有 18，000 磅的重量容量和 130，000 磅的货品要交付。
多个背包：您有五辆卡车，并且要装载具有最大重量的物品的子集。
装箱：你有20辆卡车（足够容纳所有物品），你想使用最少的卡车，将容纳他们所有。
需要将各种权重的项打包到一组具有公共容量的 bin 中。假设有足够的垃圾箱来容纳所有项目，问题是找到足够少的。
每个项目必须放在一个 bin 中。包装在每个箱中的总重量不能超过其容量。
from __future__ import print_function from ortools.linear_solver import pywraplp def create_data_model(): """Create the data for the example.""" data = {} weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30] data['weights'] = weights data['items'] = list(range(len(weights))) data['bins'] = data['items'] data['bin_capacity'] = 100 return data def main(): data = create_data_model() # Create the mip solver with the CBC backend. solver = pywraplp.Solver.CreateSolver('bin_packing_mip', 'CBC') # Variables # x[i, j] = 1 if item i is packed in bin j. x = {} for i in data['items']: for j in data['bins']: x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j)) # y[j] = 1 if bin j is used. y = {} for j in data['bins']: y[j] = solver.IntVar(0, 1, 'y[%i]' % j) # Constraints # Each item must be in exactly one bin. for i in data['items']: solver.Add(sum(x[i, j] for j in data['bins']) == 1) # The amount packed in each bin cannot exceed its capacity. for j in data['bins']: solver.Add( sum(x[(i, j)] * data['weights'][i] for i in data['items']) <= y[j] * data['bin_capacity']) # Objective: minimize the number of bins used. solver.Minimize(solver.Sum([y[j] for j in data['bins']])) status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: num_bins = 0. for j in data['bins']: if y[j].solution_value() == 1: bin_items = [] bin_weight = 0 for i in data['items']: if x[i, j].solution_value() > 0: bin_items.append(i) bin_weight += data['weights'][i] if bin_weight > 0: num_bins += 1 print('Bin number', j) print(' Items packed:', bin_items) print(' Total weight:', bin_weight) print() print() print('Number of bins used:', num_bins) print('Time = ', solver.WallTime(), ' milliseconds') else: print('The problem does not have an optimal solution.') if __name__ == '__main__': main()结果是需要4个箱子来装。
Bin number 0 Items packed: [1, 5, 10] Total weight: 87 Bin number 1 Items packed: [0, 6] Total weight: 90 Bin number 2 Items packed: [2, 4, 7] Total weight: 97 Bin number 3 Items packed: [3, 8, 9] Total weight: 96 Number of bins used: 4.0 Time = 62 milliseconds
