0-1 knapsack 배낭 문제 해법 반드시 알아야하는 디테일(물건을 중복해서 담는 경우)

12865번: 평범한 배낭 (acmicpc.net)

 

최대 한도 무게가 K로 정해진 가방 1개에 무게가 W이고 가치가 V인 N개의 물건을 담고자 할때, 가치가 최대가 되도록 담고자 한다.

 

당연히 하나의 물건은 가방에 한번만 담을 수 있다

 

 

1. 1차원 배열

 

DP[i] = 가방에 담긴 물건들의 무게 합이 i일때, 가치의 최댓값

 

DP[i] = max(DP[i], DP[i-w] + v)

 

dp = [0]*(K+1)

for w,v in bag:

    for i in range(K,-1,-1):
        
        if i-w >= 0:
            
            dp[i] = max(dp[i], dp[i-w] + v)

print(dp[K])

 

 

주목할 부분은 무게 i = 0,1,2,3,..,K가 아니라 i = K,K-1,K-2,...,0 순으로 돌았다는 것이다

 

다음과 같이 순방향으로 돌면 무슨 문제가 생기는가

 

dp = [0]*(K+1)

for w,v in bag:

    for i in range(K+1):
        
        if i-w >= 0:
            
            dp[i] = max(dp[i], dp[i-w] + v)

print(dp[K])

 

 

물건 1을 담았더니 dp[0] = 0, ... , dp[w] = A, ...로 업데이트 되어가지고

 

이제 물건 2가 무게가 w 가치가 v여서 이 물건을 담을려고 할 때,

 

i = w이면 dp[w] = max(dp[w], dp[0] + v)으로, 우연히 dp[0]+v > dp[w]여서 dp[w] = dp[0]+v = v로 담아졌다고 하자.

 

이제 i = 2w이면 dp[2w] = max(dp[2w], dp[w] + v)으로, dp[2w]와 dp[w] + v를 비교해서 물건 2를 담을지 말지 결정해야하는데,

 

이미 dp[w]에서 갱신할때, 물건 2를 담아버렸다.

 

따라서 우연히 dp[2w]  < dp[w] + v이면, dp[2w]에는 물건 2를 2번이나 담게 된다

 

---------------------------------------------------------------------------------------------------------------------------------------------------

 

그러면 이번엔 무게를 먼저 for문으로 순회하고 물건을 순회한다면

 

dp = [0]*(K+1)

for i in range(K,-1,-1):

    for w,v in bag:
    
        if i-w >= 0:
            
            dp[i] = max(dp[i], dp[i-w] + v)

print(dp[K])

 

 

어떤 무게 i에 대하여, 물건들을 순회해서 현재 dp의 크기를 비교한 다음, 물건을 담을 때 크기가 커지면 갱신해주는 순서

 

크기를 갱신한다는 것은 이미 물건 A가 담겨진 dp[i]에서 현재 보고 있는 물건 B를 담을려고 하는 것이기 때문에

 

이렇게 순회하면 하나의 dp[i]에 물건이 오직 하나만 담기게 된다.. 완전히 틀린 솔루션

 

------------------------------------------------------------------------------------------------------------------------------------------------------

 

그래서 dp를 1차원 배열 dp[i] = 현재 가방에 담긴 무게가 i일때, 담긴 물건 무게의 가치 합의 최댓값으로 정의하면

 

물건을 먼저 순회하고 무게는 역순으로 순회해줘야한다

 

dp = [0]*(K+1)

for w,v in bag:

    for i in range(K,-1,-1):
        
        if i-w >= 0:
            
            dp[i] = max(dp[i], dp[i-w] + v)

print(dp[K])

 

 

2. 2차원 배열

 

굳이 무게를 정방향으로 순회하고 싶다면 2차원 배열을 이용할 수 있다

 

dp[i][j] = 물건 i까지 봤을때, 가방에 담긴 물건 무게 합이 j인 경우 가치 합의 최댓값으로 정의하면

 

무게를 정방향으로 순회할 수 있다

 

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

 

dp[i-1][j]는 물건 i를 담지 않은 경우, i를 담더라도 가치 합의 최댓값이 바뀌지 않아 담을 필요 없는 경우

 

dp[i-1][j-w] + v는 j-w 에서 물건 i를 담은 경우

 

1차원 배열로 했을때, 물건 i를 담는 경우 j = w에서 물건 i를 담고 나서 j = 2w에서 또 물건 i를 담게 되는 경우가 생겼는데

 

dp[i-1][j-w] + v는 물건 i가 안담긴 경우로 명확하게 명시할 수 있으므로 물건 i를 2번 담는 경우를 방지할 수 있다

 

dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1):
    
    w,v = bag[i-1]
    
    for j in range(k,-1,-1):
        
        if j-w >= 0:
            
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        
        else:
            
            dp[i][j] = dp[i-1][j]

 

 

j-w < 0인데 dp[i][j] = dp[i-1][j]를 하는 이유?

 

i번째 물건까지 봤을때, i번째 물건을 담지 못하면 dp[i][j] = dp[i-1][j]로 서로 같으니까

 

논리적으로 생각해보면 명확하다

 

하지 않으면 dp[i][j] = 0으로 아무것도 안담은 것이 되니까.. 틀림

 

 

3. 한번 담은 물건을 또 담을 수 있다면

 

6066번: Buying Hay (acmicpc.net)

 

H파운드의 건초를 사고 싶은데, N개의 건초가 각각 P파운드이고 비용이 C이다.

 

각각의 건초는 무한히 구입할 수 있으며, 적어도 H파운드의 건초를 사는데 최소 비용을 구한다면?

 

 

무게 제한이 H이며 각각의 물건이 무게가 P이고 비용이 C일때, 

 

적어도 H 이상이 되도록 가방에 담는데, 비용이 최소가 되도록 하려면?

 

위 문제와 다른 점은 최대 H가 아니고 H이상이 되어도 좋다

 

그리고 각각의 물건을 1번 담더라도, 또 담을 수 있다.

 

이는 위에서 배운, "무게를 순방향으로 순회하면 물건이 중복해서 담기는 문제"를 이용한다면

 

이번에는 무게를 역방향이 아니라 순방향으로 순회하면 된다는 것을 알 수 있다

 

또한 최소 비용을 구해야하기 때문에 dp[i+w] = min(dp[i+w], dp[i] + c)로 점화식을 구해줘야겠고

 

또한, H이상이 되도록 담을 수 있기 때문에, 만약 현재 무게 i와 담을려는 물건의 무게 w의 합이 h를 넘는다면?

 

그냥 dp[h] = min(dp[h], dp[i]+c)로 해주면 되겠다.

 

#한번 담은 물건을 또 담을 수 있는 배낭문제
#무게 제한이 h이상인 경우

from sys import stdin

n,h = map(int,stdin.readline().split())

bag = []

for _ in range(n):
    
    p,c = map(int,stdin.readline().split())
    bag.append((p,c))

INF = 2500000000
dp = [INF]*(h+1)
dp[0] = 0

for w,c in bag:
    
    for i in range(h+1): #무게를 순방향 i = 0,1,2,..,h으로 순회하면 이미 담은 물건을 또 담을 수 있다

        if i + w <= h:
            
            dp[i+w] = min(dp[i+w],dp[i] + c)
        
        else:
            #최소 h 이상을 담을 수 있으므로
            #현재 무게 i + 담은 물건 무게 w > h이면, h로 하면 된다
            dp[h] = min(dp[h], dp[i] + c)

print(dp[h])