[Python][DP/knapsack] 평범한 배낭 - 백준 12865번

[문제] 

출처 : 백준 https://www.acmicpc.net/problem/12865

 

[알고리즘]

• Dynamic Programming의 대표적인 문제 Knapsack 알고리즘이다. 
  
  • N개의 물건을 1번씩 접근한다.
  • 각 물건마다 무게 1부터 채울 수 있는 최대 무게(K)까지의 최대 가치를 저장하는 방식이다. 
  • 물건마다, 무게마다의 최대 가치를 저장하는 2차원 배열(d)을 사용한다. 
• 물건의 개수는 N, 최대 무게는 K, 물건마다의 무게는 W 리스트, 가치는 V 리스트에 저장한다. 그리고 이차원 배열 d를 생성하여 이로부터 최대 가치를 획득한다. 
• 각 물건마다 다음을 i 변수를 사용하여 반복한다. (N번)
  • 1부터 저장할 수 있는 최대 무게까지 w 변수를 사용하여 반복한다. (K번)
    •  w가 현재 물건 i의 무게(W[i])보다 작을 시, 현재 물건 i의 w일때의 최대 가치(d[i][w])에 다음을 저장한다. 
      • 이전 물건일 때의 최대 가치(d[i-1][w])를 저장한다.
        (이때, 이전 물건일 때의 최대 가치와 비교하는 것은 이는 w일때의 현재까지 계산된 최대 가치이기 때문이다.)  
    • 그렇지 않을 시 
      • w의 현재까지 계산된 최대 가치(d[i-1][w])와, 현재의 물건 i의 가치(V[i])와 w에서 현재 물건의 무게를 뺀 현재까지의 최대 가치(d[i-1][w-W[i])의 합(V[i] + d[i-1][w-W[i]])과 비교한다. 
        (이때, w에서 현재 물건의 무게를 뺀 현재까지의 최대 가치와 비교하는 것은 이는 현재 물건을 더했을 때의 경우이고, 무게 w를 맞춰야 하기 때문이다. 그러므로 현재 물건의 무게 W[i]의 가치(V[i])와 나머지 w-W[i] 일 때의 최대 가치의 합과 비교해야 한다.)
        
        
      • w의 현재까지 계산된 최대 가치가 크다면, (아래 표 색상)
        
        • 이를 그대로 저장한다.
      • 그렇지 않다면, (아래 표 색상)
        • 현재의 물건 i의 가치(V[i])와 w에서 현재 물건의 무게를 뺀 현재까지의 최대 가치(d[i-1][w-W[i])의 합을 저장한다. 

Test case에 대한 행렬값은 찾아보기 힘들어, 직접 만들어보았다. 

 

[느낀점 / 깨달은 점]

• 개인적으로 너무 아쉽다. 지금까지 풀었던 Dynamic Programming에 사용된 행렬은 1차원 행렬이었고, 2차원 행렬을 사용해야할 문제에서는 풀지 못했다. 
• 이와 같은 문제를 접근할 시 1부터 최대 무게까지의 최대 가치 저장 공간을 만들어야한다는 생각이 필요하다고 생각된다. 이 생각이 쉽지 않다고 생각한다.
  • 보통은 물건마다의 저장 공간을 생각하는데 좀 더 아이디어 확장하여 2차원 행렬,  각 물건 마다 각 저장할 무게마다의 값을 저장하는 행렬을 생각해야 한다. 

N, K = map(int, input().split())

W = []
V = []
d = [[0] * (K+1) for _ in range(N)]

 
for _ in range(N):
    x, y = map(int, input().split())
    W.append(x) 
    V.append(y)

for i in range(N):
    for w in range(1, K+1):
        if w < W[i] : 
            d[i][w] = d[i-1][w]
        else : 
            if d[i-1][w-W[i]] + V[i] > d[i-1][w] :
                d[i][w] = d[i-1][w-W[i]] + V[i]
            else :
                d[i][w] = d[i-1][w]

print(d[N-1][K])