배낭 문제와 탐욕 알고리즘

  • 배낭 문제 (Knapsack Problem)

    • 도둑이 30kg까지 담을 수 있는 배낭을 메고 곡식 창고에 침투함
    • 창고 입구에는 보관 중인 곡식 전체 수량과 1kg당 가격이 적혀 있음
    • 이익이 최대가 되도록 배낭을 채우는 문제

  • Greedy approach로 배낭 문제를 해결해보기

    • 가장 값어치가 높은 아이템을 먼저 채우는 것
    • 1kg당 기준 가격을 내림차순으로 정렬
    • 배낭의 무게를 초과하지 않을 때 까지 비싼 순으로 채우기

파이썬으로 배낭 문제 구현하기(Greedy)

1
2
3
4
5
6
7
8
9
10
11
12
# W: 배낭 무게, w: 각 아이템의 무게 p:각 아이템의 값어치
def knapsack1 (W, w, p):
    n = len(w) - 1
    K = [0] * (n + 1)
    weight = 0
    for i in range(1, n + 1):
        weight += w[i]
        K[i] = w[i]
        if (weight > W):
            K[i] -= (weight - W)
            break
    return K

  • Greedy approach는 최적해를 보장하는가?

    • 아이템이 분할 가능하여 30kg를 딱 맞춰서 채울 수 있다면 가능
    • 분할이 불가능한 0-1 배낭 문제는 최적해를 보장하지 않음
    • 배낭의 용량을 넘지 않으면서 가치가 최대가 되는 S의 부분집합 A를 찾기
    • 동적계획법 or 백트랙킹 or 분기한정법으로 해결

  • Dynamic programming으로 0-1 배낭문제를 해결해보기

    • P[i][w]: 총 무게가 w를 초과할 수 없다는 제약조건 하에서 처음 i개 아이템에서만 선택할 때 얻는 최적의 이익
    • P[n][w]: n개의 아이템으로 얻을 수 있는 최대 이익
    • P[i][w] = max(P[i-1][w], pi + P[i-1][w-wi]) (단, wi ≤ w)
      or P[i-1][w] (단, wi > w)
    • max(P[i-1][w], pi + P[i-1][w-wi])
    • P[i-1][w]: i번째의 아이템까지 무게 합(wi)이 총 무게보다 크다면 해당 i번째의 아이템을 제외한 무게 합이 된다
    • P[n][W]를 계산할 때엔 P[n-1][W], P[n-1][W-Wn]만 필요하고 P[i][w]를 계산할 때엔 P[i-1][w], P[i-1][w-wi]만 필요함

파이썬으로 배낭 문제 구현하기(DP)

1
2
3
4
5
6
7
8
9
def knapsack2(i, W, w, p):
    if (i <= 0 or W <= 0):
        return 0
    if (w[i] > W):
        return knapsack2(i - 1, W, w, p)
    else:
        left = knapsack2(i - 1, W, w, p)
        right = knapsack2(i - 1, W - w[i], w, p)
        return max(left, p[i] + right)
  • backtracking로 0-1 배낭문제를 해결해보기
    • 부분집합의 합 문제와 동일하게 상태공간트리를 구성하여 최적해를 찾아 최적해의 전체 이익을 계산
1
2
3
4
5
6
7
def checknode (node):
    node u
    if (v값이 최적값보다 낫다면):
        best = v
    if (promising(v)):
        for (v의 자식을 돌며):
            노드를 체크()
  • promising과 가지치기
    • 배낭에 더이상 담을 공간이 없다면 유망하지 않음(weight >= W)
    • 현재까지 찾은 최적해의 이익이 현재 노드에서 앞으로 얻을 수 있는 최대 이익보다 크다면 유망하지 않음
      → 앞으로 얻을 수 있는 최대 이익 <= 현재까지 찾은 이익값

파이썬으로 배낭 문제 구현하기(backtracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def knapsack3 (i, profit, weight):
    global maxprofit, numbest, bestset
    if (weight <= W and profit > maxprofit):
        maxprofit = profit
        numbest = i
        bestset = include[:]
    if (promising(i, profit, weight)):
        include[i + 1] = True
        knapsack3(i + 1, profit + p[i+1], weight + w[i+1])
        include[i + 1] = False
        knapsack3(i + 1, profit, weight)

def promising(i, profit, weight):
    if (weight > W):
        return False
    else:
        j = i + 1
        bound = profit
        totweight = weight
        while (j <= n and totweight + w[j] <= W):
            totweight += w[j]
            bound += p[j]
            j += 1
        k = j
        if (k def knapsack3 (i, profit, weight):
    global maxprofit, numbest, bestset
    if weight <= W and profit > maxprofit:
        maxprofit = profit
        numbest = i
        bestset = include[:]
    if promising(i, profit, weight):
        include[i + 1] = True
        knapsack3(i + 1, profit + p[i+1], weight + w[i+1])
        include[i + 1] = False
        knapsack3(i + 1, profit, weight)


def promising(i, profit, weight):
    if weight > W:
        return False
    else:
        j = i + 1
        bound = profit
        totweight = weight
        while j <= n and totweight + w[j] <= W:
            totweight += w[j]
            bound += p[j]
            j += 1
        k = j
        if k <= n:
            bound += (W - totweight) * p[k] / w[k]
        return bound > maxprofit