[알고리즘/DP] 12865번 : 평범한 배낭 - python

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

12865번: 평범한 배낭

 

---

• 문제
• 소요시간: 31분 25초

---

• 설계하기(접근방법) 

1. 입력받기

무게와 가치를 입력받는다

 

2. 구현하기

 

이 문제는 최대 무게까지

각 무게별로 어떻게 넣어야

최대의 가치가 되는지 구하면 된다

 

즉 검사를 할 때

dp[i + w] < dp[i] + v 일때

dp[현재 무게 + 넣을 물건의 무게]의 값어치가

dp[현재 무게] 의 값어치 + 넣을 물건의 값어치 보다 작다면 

dp[i + w] = dp[i] + v 로 초기화 한다

 

최대 무게가 15,

무게와 가치가

[3,6]

[3,8]

[4,2]

[5,9] 인 배낭이 있다고 하자

 

1) 먼저 [3, 6]에 대해서

dp 0부터

0 0

1 0

2 0

3 6이 될것이다

그 이후의 무게도 3키로를 담을 수 있으니

4 6

5 6..... 초기화 해준다

 

2)  다음 가방이다 : [3,8]

0 0

2 0

3 8 -> 이전의 같은 dp 보다 가치가 뛰어나니 초기화 한다

4 8

5 8

6 14 -> 이전의 가치를 포함해주어야 한다

 

문제는 앞에서부터 순차적으로 초기화를 한다면

그 이전의 저장되어 있던 무게와 가치가 초기화 될 수 있다는 것이다

따라서 배열을 뒤에서부터 순회하면 문제를 해결할 수 있다

 

맨 처음 dp를 다시 가져와서

(원래는 최대 무게부터 검사해야한다(

7 6

6 8 

5 8

4 8 -> 7 8을 초기화(

3 6 -> (3 +3)번째 무게(6)의 값어치 8보다 (6 + 8) 이 크니 초기화 -> 6 14

2 0

1 0

0 0 -> (0 + 3) 번째 무게 초기화 -> 3 8

 

이런식으로 각 아이템별로 뒤에서부터 dp를 순회하며 초기화 하면

최대의 값을 얻을 수 있다

 

 

3. 출력하기

max(dp)를 출력한다

 

 

---

• 코드(출력)

n, weight_max = map(int, input().split())

dp = [0] * (weight_max + 1)

items = []

for i in range(n):
    w, v = map(int, input().split())
    items.append([w, v])

for item in items:
    w, v = item
    visited = [0] * (weight_max + 1)
    for i in range(weight_max, -1, -1):
        if i + w <= weight_max :
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

print(max(dp))

---

• 얻어갈 부분

1. 아이디에이션까지 잘 했고 역순으로 풀어 오류를 방지했다. dp, 그리디는 거꾸로도 생각을 항상 하자