[python3] 12865번: 평범한 배낭

풀이 일자: 23.02.20

난이도: [Gold V]

분류: [DP, 0-1 Knapsack]

문제 내용

=> 일반적인 Knapsack Problem 문제이다.

 

 

문제 해결 흐름

1. 무게당 가치를 각각 계산해서 Greedy하게 처리할 수 있지 않을까?

→ 만약 해당 문제가 fractional knapsack이었다면 가능하지만 0-1 Knapsack 즉, 물건을 쪼갤 수 없는 상태이기 때문에 Greedy알고리즘으로 처리할 수 없다.

 

주어진 예제를 보면 바로 확인이 가능한데.

MaxWeight = 7이고  (6,13), (4,8), (3,6), (5,12)의 (weight, value)쌍이 존재한다면.. 각 무게당 value 계산시 13/6 = 2.1 8/4 = 2 6/3 = 2 12/5 = 2.4 으로 Greedy하게 처리하는 경우 1. 2.4 value/weight를 가지는 5kg의 물건을 먼저 넣는다 2. 나머지 물건들은 넣는 경우 모두 최대중량에 걸리기 때문에 넣지 못한다. ( 5kg을 넣으면 남는 건 2kg인데 없으므로...) 3. 결과적으로 12가 나오게 된다. 실제 답은 12가 아닌 4kg짜리 하나와 3kg짜리 하나를 집어넣었을 때의 가치인 14이다.

 

2. 그렇다면 DP를 이용해서 처리를 해야겠다.

→ DP를 위해 우선 점화식을 찾아보자.  우선 2차원 배열 dp[i][w]를 선언하고 row는 각 물건을 의미 col은 무게를 의미하도록 한다.

 

dp[i][w] = (0 ~ i)번째 물건을 중복해서 0개 이상 넣고 무게 w를 넘지 않았을 때의 최대 가치

 

1) 만약 i번째 물건이 w보다 무게가 많이 나가는 경우 i번째 물건은 넣을 수 없다.

→ 이전 row의 값을 그대로 집어넣는다.

dp[i][w] = dp[i-1][w];

 

2) 만약 i번째 물건이 w보다 무게가 적게 나가는 경우

→ i번째 물건을 1개이상은 꼭 넣었을 때와 넣지 않았을 때의 최대값을 골라서 dp[i][w]에 넣는다.

dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);

 

위의 idea를 코드로 변환하면

n, k = map(int, input().split());

weights = list();
values = list();

for i in range(n):
    w, v = map(int, input().split());
    weights.append(w);
    values.append(v);
    
dp = [[0 for i in range(k + 1)] for _ in range(n + 1)];

for i in range(1, n + 1):
    for w in range(1, k + 1):
        if weights[i-1] > w:
            dp[i][w] = dp[i-1][w];
        else:
            dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);

print(dp[n][k]);

Time Complexity: O(N*K)

dp의 특성상 메모리제이션을 통한 답을 쌓아가면서 최종 정답을 내기 때문에 N*K만큼의 반복이 필요하다.

 

Space Complexity: O(N*K)

dp를 1차원으로 정의한다면 N이였겠지만 우선 이해와 편의를 위해 2차원으로 설정했기에 N*K만큼의 공간이 필요하다.

 

 

다른 해결 방식(다른 사람 풀이 참고)

1. 굳이 2차원으로 배열을 선언하지 않더라도 풀 수 있을 것이다.

→ 내부 for문을 k부터 w까지로 돌리는 이유는 어차피 현재 물건의 무게가 j보다 작다면 기존 값을 유지하고 뒤에 있는 값들은 앞의 인덱스에 있는 값을 사용하기 때문에 뒤에서부터 처리해주어야 한다.

n, k = map(int, input().split());

wv = [tuple(map(int, input().split())) for _ in range(n)];
dp = [0 for i in range(k + 1)];

for i in range(1, n + 1):
    w, v = wv[i-1];
    for j in range(k, w - 1, -1):
        dp[j] = max(dp[j], v + dp[j - w]);

print(dp[k]);

 

2. Sort를 해서 줄이는 방법

→ 물건의 무게로 sort를 해서 2차원 배열의 역삼각형 부분만 계산해도 되도록 만들어진 풀이이다.

N,K = map(int,input().split())  # 물품수, 최대무게

dp = [[0 for _ in range(N)] for _ in range(K+1)]
item = []
for _ in range(N):
    w, v  = map(int,input().split())
    item.append((w,v))

item.sort(key=lambda x:x[0],reverse=True)

for n in range(N):
    w,v = item[n]
    for i in range(w,K+1):
        if n >= 1:
            dp[i][n] = max(dp[i][n-1], dp[i-w][n-1] + v)
        else:
            dp[i][n] = max(dp[i-1][n], v)
print(dp[K][-1])

 

문제 링크

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

12865번: 평범한 배낭