[OR-Tools 스터디] The Knapsack Problem

knapsack 문제에서는, 값과 크기(무게나 부피)가 주어진 사물들을 최대 용량의 container에 넣어 포장해야한다.

만약 사물들의 전체 크기가 용량을 초과한다면, 모든 사물들을 포장할 수 없게 된다.

이러한 경우, container에 들어갈 최대 총 값의 항목 중 부분 집합을 선택하는 것이 문제다. 

 

따르는 섹션에서 OR-Tools을 사용한 knapsack problem을 어떻게 푸는지 보여준다.

 

Example

50개의 사물들이 박스에 포장된다. 각 사물들은 값과 무게를 가지고 있다. 박스는 850의 용량을 가지고 있다고 선언되었으며, 우리의 목표는 용량을 초과하지 않고 전체 값을 최대화 시키는 사물의 집합을 찾는 것이다.

 

from ortools.algorithms import pywrapknapsack_solver

def Knapsack():
    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]

    #declare the solver
    solver = pywrapknapsack_solver.KnapsackSolver(
        pywrapknapsack_solver.KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackExample'
    ) #KNAPSAK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER : solver에게 문제를 해결하기 위해 branch and bound 알고리즘을 쓰라고 말해주는 것.
    # b&b 알고리즘 : 각 노드를 방문할 때 마다 그 노드가 유망한지의 여부를 결정하기 위해 bound를 계산함.
    #bound는 그 노드로부터 branch해서 얻을 수 있는 해답치의 한계를 나타내며, 만약 bound가 지금까지 찾은 최적의 해답치보다 좋지 않은 경우는 서브 트리를 pruning한다.
    #backtracking은 계속 가보면서 진행 여부를 결정하는 반면, b&b는 최적해를 찾을 가능성이 없으면 분기하지 않음.

    #call the solver
    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)


    #프로그램에서 먼저 solver를 초기화 시킨 후, computed_value = solver.Solver()로 호출한다.
    #최적의 솔루션의 전체 값은 computed_value이며, 이 케이스의 경우 전체 무게와 동일하다.
    #이 프로그램은 밑에 따르는 솔루션에서 포장된 사물들의 인덱스들을 얻을 수 있다.
    #
    # packed_items = [x for x in range(0, len(weights[0]))
    #                 if solver.BestSolutionContains(x)
    #                 ]
Knapsack()

 

Reference:

https://developers.google.com/optimization/pack/knapsack

배낭 문제  |  OR-Tools  |  Google Developers