가방이 여러개인 multiple 0-1 knapsack(배낭 문제) 해법 배우기

1. 다중 배낭 문제(multiple 0-1 knapsack)

 

https://atcoder.jp/contests/past202206-open/tasks/past202206_h

H - Two Knapsacks

 

 

각각 무게 제한이 A,B인 2개의 가방이 있다고 하자.

 

이 2개의 가방에 무게가 W, 가치가 V인 물건을 담고자 한다.

 

2개의 가방에 담긴 물건 가치 합이 최대가 되도록 하는 방법은?

 

처음에는... 단순히 무게 제한이 A인 가방에 물건을 담고, 담은 물건은 제외한 다음 무게 제한이 B인 가방에 물건을 담는 식으로

 

for문을 2번 돌리는거지

 

n,a,b = map(int,input().split())

bag = []

for _ in range(n):
    
    w,v = map(int,input().split())
    bag.append((w,v))

value = 0

visited = [0]*(n)

for m in [a,b]:
    
    dp = [[0,[]] for _ in range(m+1)]

    for j in range(n):
        
        if visited[j] == 0:

            w,v = bag[j]
            
            for i in range(1,m+1):
                
                if i - w >= 0 and j not in dp[i-w][1]:
                    
                    if dp[i-w][0] + v > dp[i][0]:

                        dp[i][1] = dp[i-w][1][:]
                        dp[i][1].append(j)
                        dp[i][0] = dp[i-w][0] + v

    for j in dp[m][1]:

        visited[j] = 1

    value += dp[m][0]

print(value)

 

 

근데 이렇게 하면 틀리더라고

 

우연히 무게 제한이 A인 가방에 담긴 물건이 무게 제한이 B인 가방에 담길 때 가치가 최대일 수도 있으니까

 

무게 제한이 서로 같으면 맞을 것 같기는 한데 모르겠다...

 

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

 

결론은 모든 경우를 다 따져봐야 한다는 것

 

dp[i][j] = 첫번째 가방(무게 제한이 A)에 담긴 물건 무게 합이 i이고 두번째 가방(무게 제한이 B)에 담긴 물건 무게 합이 j일때 물건 가치의 합의 최댓값으로 정의

 

i = a,a-1,a-2,...,0으로 순회하고 j = b,b-1,b-2,..,0으로 순회하면서..

 

현재 보는 물건의 무게가 w, 가치가 v일때 i >= w, j >= w이면 두 가방에 담을 수 있으므로

 

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

 

i >= w이지만 j < w이면 첫번째 가방에만 담을 수 있으므로

 

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

 

i < w이지만 j >= w이면 두번째 가방에만 담을 수 있으므로

 

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

 

dp = [[0]*(b+1) for _ in range(a+1)]

for w,v in bag:

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


print(dp[a][b])

 

 

 

가방 1개일때와 똑같은 이유로  i = 0,1,2,..,a, j = 0,1,2,..,b 순방향으로 순회하면 물건이 중복해서 담길 수 있으므로 오답

 

dp[i][j][k]를 i번째 물건까지 봤을때, 첫번째 가방 무게 합이 j, 두번째 가방 무게 합이 k일때 물건 가치 합의 최대로 정의한다면

 

순방향으로 순회해서 해결할 수 있다

 

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

for i in range(1,n+1):
    
    w,v = bag[i-1]

    for j in range(a+1):
    
        for k in range(b+1):
            
            if j-w >= 0 and k-w >= 0:

                dp[i][j][k] = max(dp[i-1][j-w][k] + v, dp[i-1][j][k-w] + v, dp[i-1][j][k])
            
            elif j-w >= 0:
                
                dp[i][j][k] = max(dp[i-1][j-w][k] + v, dp[i-1][j][k])
            
            elif k-w >= 0:
                
                dp[i][j][k] = max(dp[i-1][j][k-w] + v, dp[i-1][j][k])
            
            else:
                
                dp[i][j][k] = dp[i-1][j][k]


print(dp[n][a][b])

 

 

가방이 3개이면 어떻게 할까?

 

dp[i][j][k]로 첫번째 가방의 무게 합이 i, 두번째 가방 무게 합이 j, 세번째 가방 무게 합이 k일 때 가치 합의 최댓값으로 하고

 

위와 똑같이 하면 되겠지

 

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

 

 

2. 비슷한 문제

 

15188번: Packing (acmicpc.net)

 

가방 무게 제한이 w1, w2인 2개의 가방에 물건을 담을때 가치 합이 최대가 되도록 담는 문제로 위와 똑같은 문제다

 

 

#가방이 여러개인 배낭 문제

from sys import stdin

P = int(stdin.readline())

for p in range(1,P+1):
    
    #첫번째 가방 무게 제한이 w1, 두번째 가방 무게 제한이 w2
    n,w1,w2 = map(int,stdin.readline().split())

    W = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    #dp[i][j] = 첫번째 가방에 담긴 물건 무게 합이 i, 두번째 가방에 담긴 물건 무게 합이 j
    #일때 물건 무게 가치 합의 최댓값
    dp = [[0]*(w2+1) for _ in range(w1+1)]

    for i in range(n):
        
        w = W[i]
        v = V[i]
        
        #역순으로 순회해야 물건이 중복해서 안담김
        for j in range(w1,-1,-1):
            
            for k in range(w2,-1,-1):
                
                if j-w >= 0:
                    
                    dp[j][k] = max(dp[j-w][k] + v, dp[j][k])
                
                if k-w >= 0:
                    
                    dp[j][k] = max(dp[j][k-w] + v, dp[j][k])
    
    print(f'Problem {p}: {dp[w1][w2]}')