Knapsack(배낭 문제)

배낭 문제

배낭 문제란 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제.

Fraction Knapsack
Fracktion Knapsack 문제는 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다.
남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라 넣으면 된다.
→ Greedy로 해결 가능

0-1 Knapsack
0-1 Knapsack 문제는 물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다.
→ DP로 해결 가능

 

0-1 Knapsack(평범한 배낭)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

• 물건의 무게와 가치가 주어지고, 담을 수 있는 배낭의 최대 용량이 주어진다고 가정
• 이 때, 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 구하라.
• 다음과 같이 물건의 정보가 주어진다.

dp[i][j]를 다음과 같이 정의한다.

dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최댓값

이 경우 1부터 N개의 모든 물건들을 살펴보고, 배낭 용량이 K였을 때 이 배낭에 들어가 있는 물건들의 가치합의 최댓값이 dp[i][j]에 들어가게 된다.

점화식

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

• i번째 물건을 배낭에 넣으려 한다. 이 때 배낭의 용량은 j이다.
• 용량이 j인 배낭에 i번째 물건을 넣지 않았을 때의 가치합의 최댓값은 dp[i-1][j]이다.

      -> dp[i-1][j]의 값은 배낭의 용량이 j이고, i-1번째 물건까지 살펴봤을 때의 가치합의 최댓값

• 용량이 j인 배낭에 i번째 물건을 넣었을 때의 상황은 dp[i-1][j-w[i]] + v[i]이다,

      -> i-1번째 물건까지 살펴보았고 배낭의 용량이 j-w[i]였을 때의 값에 새롭게 i번째 물건을 넣은 상황이 된다.

 

=> 쉽게 말해, i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 더 가치가 큰 것을 가져오면 되는 것!

평범한 배낭

[Step 0] 행은 물건의 index, 열은 배낭의 용량으로 2차원 배열을 생성한다.

[Step 1] 첫 번째 물건(W : 6, V : 13)을 채워넣는다.

[Step 2]  두 번째 물건(W : 4, V : 8)을 채워넣는다.

[Step 3]  세 번째 물건(W : 3, V : 6)을 채워넣는다.

[Step 4]  네 번째 물건(W : 5, V : 12)을 채워넣는다.

 

0-1 Knapsack(평범한 배낭) - Code

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
array = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
# 1. 2차원 배열 생성하기
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
# 2.
for i in range(1, n+1) :
    for j in range(1, k+1) :
        w = array[i][0]
        v = array[i][1]
        # 2-1. j(무게) < w 일 경우
        if j < w :
            dp[i][j] = dp[i-1][j]
        # 2-2. 그 외의 경우
        else :
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
# 3. 결과 출력
print(dp[n][k])

 

최적화된 0-1 Knapsack(평범한 배낭)

• dp를 2차원 배열을 사용하지 않고, 1차원 배열로 사용하는 방법
• 기존의 2차원 배열은 가방 용량을 1부터 k까지 작은 쪽부터 큰 쪽의 순서로까지 살펴봄
• 1차원 dp 배열은 가방 용량을 k부터 1까지 큰 쪽에서 작은 쪽의 순서로 살펴봄

      -> 기존의 점화식 사용 : dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

 

[Step 0] (k+1) 길이의 1차원 배열을 생성한다.

[Step 1] 첫 번째 물건(W : 6, V : 13)을 채워넣는다.

[Step 2]  두 번째 물건(W : 4, V : 8)을 채워넣는다.

[Step 3]  세 번째 물건(W : 3, V : 6)을 채워넣는다.

[Step 4]  네 번째 물건(W : 5, V : 12)을 채워넣는다.

 

최적화된 0-1 Knapsack(평범한 배낭) - Code

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
array = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)]
# 1. 2차원 배열 생성하기
dp = [0 for _ in range(k+1)]

# 2.
for i in range(n+1) :
    for j in range(k, -1, -1) :
        w = array[i][0]
        v = array[i][1]
        if j >= w :
            dp[j] = max(dp[j], dp[j-w] + v)
# 3. 결과 출력
print(dp[k])

 

두 방식의 메모리, 실행 시간 비교