#392 백준 파이썬 [7579] 앱 - 냅색 알고리즘

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

 

SOLUTION

유명한 냅색 문제, 냅색 알고리즘이다.

간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

출처: 위키피디아

 

냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다.

 

담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)

담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

해당 문제는 0-1 배낭문제의 경우다.

 

이 문제는 다음과 같은 알고리즘으로 풀 수 있다. 풀어서 한 번, 식으로 한 번 설명하겠다.

 

알고리즘

dp[i][j]는 i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 byte를 의미한다.

 

1) 행은 app 개수만큼, 열은 sum(cost)만큼 만들어준다.

2) 행을 차례대로 돌며 다음과 같은 알고리즘을 수행해준다.

 

3-0) 현재 앱의 cost가 j보다 클 경우 끄지 못하므로 활성화시켜둔다.

dp[i][j] = dp[i-1][j

3-1) 그렇지 않다면 현재 앱을 끈 뒤의 byte와 그렇지 않을 경우의 byte중 큰 값을 dp에 입력한다.

dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])

4) 현재 dp[i][j] 값이 M이상이라면 현재 cost, j와 이전의 result와 비교해 더 작은 값을 취해준다.

result = min(result, j)

 

결국 아래와 같은 엑셀이 만들어진다.

		0	1	2	3	4	5	6
BYTE	COST	0	0	0	0	0	0	0
30	3	0	0	0	30	30	30	30
10	0	0	10	10	40	40	40	40
20	3	0	10	10	40	40	40	40
35	5	0	10	10	40	40	40	60
40	4	0	10	10	40	40	50	60

PYTHON CODE

N, M = map(int, input().split())
A = [0] + list(map(int, input().split())) #byte
C = [0] + list(map(int, input().split())) #cost
dp = [[0 for _ in range(sum(C)+1)] for _ in range(N+1)] #냅색알고리즘이 실행될 dp
result = sum(C) #열의 최댓값

for i in range(1, N+1):
    byte = A[i]
    cost = C[i]
    
    for j in range(1, sum(C) + 1):
        if j < cost: #현재 앱을 비활성화할만큼의 cost가 충분하지 않을 경우
            dp[i][j] = dp[i-1][j]
        else:
        	#같은 cost 내에서 현재 앱을 끈 뒤의 byte와 현재 앱을 끄지 않은 뒤의 byte를 비교
            dp[i][j] = max(byte + dp[i-1][j-cost], dp[i-1][j])
            
        if dp[i][j] >= M: #조건이 충족된다면
            result = min(result, j) #더 작은 cost값으로 갱신
if M != 0:
    print(result)
else:
    print(0)