[백준 12865번] 평범한 배낭 -python

문제 링크

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

12865번: 평범한 배낭

풀이 - 다른 블로그 참고 

- 냅색(Knapsack) 알고리즘이라 불리는 문제라고 한다. 전형적인 dp문제 

 

냅색(Knapsack) 알고리즘 이란 ?

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고,

일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 

 

- dp[n][k] : n번째 물건까지 살펴보았을 때, 무게가 k인 배낭의 최대 가치 

각각의 물건을 선택할 때마다 최대 가치를 판별해보자. 

물건을 선택할 때,

1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크면 넣지 않는다.

2. 그렇지 않으면, 다음 중 더 나은 가치 선택 

1) 현재 넣을 물건의 무게만큼 배낭에서 뺀 후, 현재 넣을 물건 넣기

2) 현재 물건을 넣지 않고 현재 배낭 그대로 가져가기 

이를 코드로 나타내면,

현재 물건의 인덱스 i, 현재 가방의 허용 용량을 j, 현재 담을 물건의 무게를 w, 가치를 v라고 할 때 

1. j < w : dp[i][j] = dp[i-1][j]

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

 

이 때, 물건의 무게는 정해져 있는데 현재 담을 물건의 무게와 똑같은 무게의 물건이 없다면 ? 

현재 넣을 물건의 무게를 뺀 배낭 d[i-1][j-w] 에는 그 무게의 배낭이 가지는 최대 가치가 저장되어 있기 때문에 상관없다. 

 

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

# 배낭의 무게와 가치 
product = [[0,0]]

# dp[n][k] : n번째 물건까지 살펴보았을 때, 무게가 k인 배낭의 최대 가치 
dp = [ [0] * (k+1) for _ in range(n+1)]

for _ in range(n):
  product.append(list(map(int,input().split())))

for i in range(1, n+1):
  for j in range(1, k+1):
    # 현재 물건의 무게
    w = product[i][0]
    # 현재 물건의 가치 
    v = product[i][1]

    # 현재 물건의 무게가 현재 배낭의 허용 무게보다 크면 
    if j < w :
        # 현재 물건 선택하지 않음 
      dp[i][j] = dp[i-1][j]
    else:
       # 현재 넣을 물건의 무게만큼 배낭에서 뺀 후, 현재 넣을 물건 넣기 vs 현재 물건을 넣지 않고 현재 배낭 그대로 가져가기 
      dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])

print(dp[n][k])

- 한 번 풀어본 거랑 안 풀어본 거랑 차이가 많이 날 것 같은 문제