-
36. 배낭문제(Knapsack problem) - 탐욕법, 동적 계획법 - 파이썬Python/파이썬 자료구조 알고리듬 2019. 6. 30. 18:57반응형
배낭 문제는 짐을 쪼갤 수 있느냐 없느냐로 나뉩니다.
쪼갤 수 있는 경우
분할 가능 배낭 문제라고 합니다.
배낭에 담을 수 있는 물건이 분할이 되면 쉽습니다. (금가루, 은가루, 철가루)
부피 (또는 무게) 대비 가치가 높은 물건들부터 담으면 되기 때문입니다.이것을 탐욕(greedy) 알고리듬이라고 합니다.
부피 대비 가치가 높은 물건 순서대로 담으면 되고,
담을 때 '뒤에 어떤 물건을 넣을지'
고려하지 않아도 되기 때문에 붙여진 이름입니다.(탐욕스럽게) 비싼 것부터 막 넣어~!
어떤 행위가 나중에 어떤 영향을 미칠 지 생각하지 않고
현재 가장 이익이 되는 행위만 취해도
최고의 결과가 나올 때
사용하는 쉬운 알고리듬입니다.동전 거스름돈의 경우도 대부분의 국가에서
탐욕 알고리듬으로 정답이 나오도록 되어 있습니다.
우리나라도 500원, 100원, 50원, 10원, 5원, 1원으로 5 단위(?)로 되어 있습니다..def count_changes(coins, money): changes = [] for coin in coins: changes.append(money // coin) money %= coin return changes print(count_changes([500, 100, 50, 10, 5, 1], 2025)) # [4, 0, 0, 2, 1, 0]만약 이 단위를 벗어난 동전(321원)이 있다면
높은 금액의 동전부터 순서대로, 최대한(=탐욕적으로)
많은 동전을 주는 알고리듬으로는 답이 나올 수 없겠죠?이런 경우도 동적계획법으로 답을 찾을 수 있습니다만..
내용이 많아 별도의 글로 올립니다.쪼갤 수 있는 경우는 너무 쉬워서 굳이 코딩을 안 해도 될 것 같습니다.
개념만...금가루 은가루 철가루 부피 1 2 3 단가 3 2 1 배낭의 여유 공간: 4
금가루 1 + 은가루 2 + 철가루 1 을 담는 것이 가장 많은 가치를 담을 수 있습니다.
쪼갤 수 없는 경우
쪼갤 수 없는 배낭 문제를 0-1 배낭 문제라고도 합니다.
부피(무게) 대비 가치가 높은 순서로 담는 게 답이 되지 않을 수 있습니다.
재귀
def knapsack(capacity, n): if capacity == 0 or n == 0: return 0 if size[n-1] > capacity: return knapsack(capacity, n-1) else: return max(value[n-1] + knapsack(capacity-size[n-1], n-1), knapsack(capacity, n-1)) size = [3, 4, 7, 8, 9] value = [4, 5, 10, 11, 13] print(knapsack(10, 5)) # 14마지막 리턴문이 모든 것을 설명합니다.
1. 하나를 배낭에 넣었을 때 가치의 증가분 + 다음 항목을 검색하는 함수(물론 공간이 줄어듬도 입력)
2. 배낭을 넣지 않고 다음을 검색하는 함수
그리고 이 둘 중 큰 값을 선택합니다.
불필요하게 전역변수를 쓰는 것은 좋지 않은 습관입니다.
프로젝트가 커지면 전역변수는 여러 가지로 불편합니다.
이렇게 몇 줄 안되는 코드에서야... 별 상관은 없습니다만..전역변수를 쓰지 않기 위한 테크닉들은
다음과 같습니다.1. 매개변수에 모두 집어넣는다.
2. 클래스를 사용한다.
3. 함수 내 함수를 사용한다.전역변수를 쓰지 않고, 매개변수를 사용했습니다.
가독성은 좋지 않지만, 이해하기는 쉽습니다.def knapsack(capacity, n, size, value): if capacity == 0 or n == 0: return 0 if size[n - 1] > capacity: return knapsack(capacity, n - 1, size, value) else: return max(value[n - 1] + knapsack(capacity - size[n - 1], n - 1, size, value), knapsack(capacity, n - 1, size, value)) print(knapsack(10, 5, [3, 4, 7, 8, 9], [4, 5, 10, 11, 13])) # 14클래스를 사용했습니다.
class Knapsack: def __init__(self, size, value): self.size = size self.value = value def tuck_into(self, capacity, n): if capacity == 0 or n == 0: return 0 if self.size[n - 1] > capacity: return self.tuck_into(capacity, n - 1) else: return max(self.value[n - 1] + self.tuck_into(capacity - self.size[n - 1], n - 1), self.tuck_into(capacity, n - 1)) knapsack = Knapsack([3, 4, 7, 8, 9], [4, 5, 10, 11, 13]) print(knapsack.tuck_into(10, 5)) # 14함수내 함수를 사용했습니다.
1번과 함수의 시그니쳐가 같기 때문에
바로 리팩토링할 수 있습니다.파이써닉하죠.
외부 함수 knapsack의 parameter(매개변수)들인 size와 value는
내부 함수 tuck_into의 전역변수처럼 사용되겠죠?이너 함수와 아우터 함수의 변수명이 같으면 좋지 않기 때문에
명확하게 capacity_, n_ 으로 언더스코어로 구분을 해 주었습니다.
이들은 리턴 행에 있는 truk_into의 argument(인자)로만 사용됩니다.def knapsack(size, value, capacity_, n_): def tuck_into(capacity, n): if capacity == 0 or n == 0: return 0 if size[n - 1] > capacity: return tuck_into(capacity, n - 1) else: return max(value[n - 1] + tuck_into(capacity - size[n - 1], n - 1), tuck_into(capacity, n - 1)) return tuck_into(capacity_, n_) print(knapsack([3, 4, 7, 8, 9], [4, 5, 10, 11, 13], 10, 5)) # 14재귀를 사용하지 않고...
2차원 배열을 만듭니다.
array[i][s]는 배낭 크기가 s일 때, i개의 물건을 넣었을 때, 가능한 최대 가치를 의미합니다.
역시 이번에도 이 2차원 배열이 문제의 해결의 핵심이 됩니다.
def knapsack1(capacity, n): array = [[0 for _ in range(capacity+1)] for _ in range(n+1)] for i in range(1, n+1): for s in range(1, capacity+1): if size[i-1] > s: # 물건의 부피가 s보다 크면 array[i][s] = array[i - 1][s] else: # 물건의 부피가 s보다 작거나 같으면 array[i][s] = max(value[i-1] + array[i-1][s-size[i-1]], array[i-1][s]) print('%2d' % array[i][s], end=' ') print() return array[n][capacity] size = [9, 3, 4, 7, 8] value = [13, 4, 5, 10, 11] print(knapsack1(10, 5))0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 4 4 4 4 0 0 0 4 5 5 5 9 9 9 9 0 0 0 4 5 5 5 10 10 10 14 0 0 0 4 5 5 5 10 11 11 14 0 0 0 4 5 5 5 10 11 13 14 14혹시 이해가 가지 않으신 다면 막대기 자르기부터 순서대로 보시는 게 좋습니다.
반응형