[백준] 12865번 : 평범한 배낭 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

12865번: 평범한 배낭

 

1. 문제 설명

2. 풀이과정

해당 문제는 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제이다.

먼저 첫 번째 물건까지만 고려하여 배낭에 넣었을 때, 무게가 6이므로 6일 때 가치가 13이다.

무게가 7인 경우에는 더 이상 넣을 물건이 없으므로 그대로 최대 가치가 13이다.

두 번째 물건까지 고려하여 배낭에 넣었을 때, 두 번째 물건의 무게가 4이므로 무게가 4일 때 최대 가치는 8이다.

무게가 5인 경우에는 두 번째 물건만 넣을 수 있으므로 역시 최대 가치는 8이다.

하지만 무게가 6인 경우에는 두 번째 물건을 넣기보다 첫 번째 물건을 넣는 것이 가치가 더 크므로 첫 번째 물건을 넣고 그 가치는 13이다.

세 번째 물건까지 고려하여 배낭에 넣었을 때, 가장 작은 무게인 세 번째 물건의 무게가 3이므로 무게가 3일 때 최대 가치는 6이다. 이후 무게가 4인 경우에는 두 번째 물건을 넣는 것이 최대 가치를 가지므로 두 번째 물건을 넣고 최대 가치는 8이다.

무게가 6인 경우에는 역시 첫 번째 물건을 넣는 것이 최대 가치를 가지므로 첫 번째 물건을 넣고 최대 가치는 13이다.

무게가 7인 경우에는 두 번째 물건과 세 번째 물건을 모두 넣을 수 있는데, 이때 첫 번째 물건만 넣는 가치보다 더 큰 가치를 갖는다. 하여 무게가 7인 경우에는 두 번째 물건과 세 번째 물건을 넣고 최대 가치는 14가 된다.

마지막 물건까지 고려하여 배낭에 넣었을 때, 무게가 3인 경우에는 세 번째 물건을 넣고, 무게가 4인 경우에는 두 번째 물건을 넣고, 무게가 5인 경우에는 마지막 물건을 넣고, 무게가 6인 경우에는 첫 번째 물건을 넣고, 무게가 7인 경우에는 두 번째와 세 번째 물건을 넣는 경우가 각 무게별로 최대의 가치를 얻을 수 있는 경우이다.

 

이렇게 앞에서부터 물건의 무게와 가치를 고려하며 얻을 수 있는 최대 가치를 구한다.

무게에 따른 최대 가치를 저장할 배열을 생성하고 물건을 차례대로 불러오며 각 무게에 따른 최대 가치를 저장한다.

가능한 최대 무게에서부터 무게를 줄여가며 각 최대 가치를 저장한다.

해당 무게에서 가능한 최대 가치는 현재 고려하는 물건 이전까지의 최대 가치와 새로 고려하는 물건을 넣었을 때, 즉 해당 무게에서 고려하는 물건의 무게를 뺀 무게의 최대 가치에 고려하는 물건의 가치를 더한 결과 중 더 큰 가치를 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 패키지를 불러온다. import sys
2. 물건의 개수와 배낭에 넣을 수 있는 최대 무게를 입력받는다. N, K = map(int, sys.stdin.readline().split())
3. 각 물건의 무게와 가치를 저장할 리스트를 생성한다. li = list()
4. 물건의 개수만큼 반복하며 for _ in range(N)
5. 물건의 무게와 가치를 입력받고 W, V = map(int, sys.stdin.readline().split())
6. 두 값을 리스트로 묶어 리스트에 추가한다. li.append([W, V])
7. 각 무게 별로 가치를 저장할 배열을 생성한다. dp = [0] * (K + 1)
8. 물건을 앞에서부터 가져오며 for i in li
9. 물건의 무게와 가치를 구분한다. W, V = i
10. 배낭에 담을 수 있는 최대 무게부터 현재 고려하는 물건의 무게까지 각 무게별 최대 가치를 저장한다. for j in range(K, W - 1, -1)
11. 해당 무게의 최대 가치는 해당 무게의 현재 최대 가치와 해당 무게에서 가져온 물건의 무게를 뺀 무게의 최대 가치에 가져온 물건의 가치를 더한 결과 중 최댓값을 저장한다. dp[j] = max(dp[j], dp[j - W] + V)
12. 모든 물건을 고려하여 배낭에 담았을 때, 담을 수 있는 물건의 최대 무게에 대한 최대 가치를 출력한다. print(dp[-1])

반응형

3. 소스코드

import sys

N, K = map(int, sys.stdin.readline().split())

li = list()
for _ in range(N):
    W, V = map(int, sys.stdin.readline().split())
    li.append([W, V])

dp = [0] * (K + 1)

for i in li:
    W, V = i

    for j in range(K, W - 1, -1):
        dp[j] = max(dp[j], dp[j - W] + V)

print(dp[-1])