냅색(Knapsack)알고리즘(배낭 문제)

1. 분할 가능한 배낭 문제 

출처: 나무위키

도둑이 열린 상자에 든 금괴를 훔쳐가려고 한다 

도둑이 가지고 있는 배낭에 담을 수 있는 총무게가 15kg이고 

금괴가 든 상자는 a상자가 12kg, b상자가 1kg, c상자가 4kg, d상자가 1kg, e상자가 2kg이 있다 

a, b, c, d 상자의 가치가 각각 $4, $2, $1, $10, $2라고 할 때 

도둑이 배낭에 담을 수 있는 최적의 조합은 

a 7kg, c 4kg, b 1kg, e 2kg, d 1kg이 된다 

 

- 그리디로 해결 

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]  # 배열 K에 현재 아이템의 가치를 저장

        if weight > W:  # 현재 무게가 무게 제한을 초과하는 경우
            K[i] -= (weight - W)  # 초과한 만큼 가치에서 차감
            break  # 루프 종료

    return K  # 최대 가치 배열 반환

 

2. 0-1 배낭 문제 

출처: 나무위키

만약 위 사례와 다르게 열리지 않은 상자에 든 금괴를 훔쳐가는 상황이면 

도둑의 배낭의 총량이 15kg인 상황에서 최적의 조합은 

c 4kg, b 1kg, e 2kg, d 1kg이다 

a는 열리지 않아서 일부만 꺼낼 수 없기 때문에 고려할 수 없다 

 

- 동적 계획법으로 해결 

def knapsack2(i, W, w, p):
    if i <= 0 or W <= 0:  # 종료 조건: i가 0 이하거나 W가 0 이하인 경우
        return 0

    if w[i] > W:  # 현재 아이템의 무게가 무게 제한을 초과하는 경우
        value = knapsack2(i - 1, W, w, p)  # 이전 아이템을 선택하지 않은 경우의 가치를 계산
        return value

    else:  # 현재 아이템의 무게가 무게 제한 내에 있는 경우
        left = knapsack2(i - 1, W, w, p)  # 이전 아이템을 선택하지 않은 경우의 가치를 계산
        right = knapsack2(i - 1, W - w[i], w, p)  # 현재 아이템을 선택한 경우의 가치를 계산
        return max(left, p[i] + right)  # 이전 아이템을 선택한 경우와 현재 아이템을 선택한 경우 중 더 큰 가치를 반환

 

3. 관련 문제 

문제 

12865번: 평범한 배낭

 

코드 

def recur(cur, w):
    global ans

    if w > m:  # 무게 제한을 초과한 경우
        return -9999999

    if cur == n:  # 마지막 아이템까지 확인한 경우
        return 0

    if dp[cur][w] != -1:  # 이미 계산한 경우
        return dp[cur][w]

    # 현재 아이템을 선택한 경우와 선택하지 않은 경우 중 더 큰 가치를 선택하여 저장
    dp[cur][w] = max(recur(cur + 1, w + arr[cur][0]) + arr[cur][1], recur(cur + 1, w))

    return dp[cur][w]

n, m = map(int, input().split())  # 아이템 개수(n)와 무게 제한(m)을 입력받음
arr = [list(map(int, input().split())) for i in range(n)]  # 각 아이템의 무게와 가치를 입력받음

dp = [[-1 for _ in range(100010)] for j in range(n)]  # 메모이제이션을 위한 배열 초기화

ans = recur(0, 0)  # 재귀 함수 호출

print(ans)  # 최대 가치 출력