2022.03.18 [백준] (python 파이썬) 평범한 배낭

 

 

 

 

 

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

12865번: 평범한 배낭

 

---

풀이

이 문제는 0-1 배낭문제(0-1Knapsack Problem)이다. 왜냐하면 물건을 나누지 못하고 가진 물건으로 가방에 넣어 최대 가치를 만들어야 하기 때문이다. 

 

dp배열을 (n+1)(k+1)배열의 크기로 만든다. 이유는 조건에 따라 이전의 값과 비교해야 해서 n,k보다 1씩 큰 배열을 만들었다.

각 물건별 각 무게로 for문을 돌면서 현재의 무게가 해당 물건의 무게보다 크면 해당 dp값은 dp[i-1][j](이전물건의 해당무게에서의 가치)와 dp[i-1][j-wv[i][0]]+wv[i][1](이전물건에서 현재가방의 무게-현재물건무게의 dp값 + 현재 물건의 가치)를 비교해서 큰 값으로 업데이트해주었다. 그러면 dp[n][k]에서 해당 가방에 물건을 넣어 만들 수 있는 최대 가치를 구할 수 있다.

n,k=map(int, input().split())
wv=[(0,0)]
dp=[[0]*(k+1) for i in range(n+1)]
for _ in range(n):
    x,y=map(int, input().split())
    wv.append((x,y))
 
 
for i in range(1,n+1):
    for j in range(1,k+1):
        if j>=wv[i][0]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-wv[i][0]]+wv[i][1])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][k])