upload: In progress
링크: https://www.acmicpc.net/problem/12865
알고리즘 개념: https://www.notion.so/DP-cb86236f695748e38b10b19d7eb5a68e
유형: 동적프로그래밍
작성일시: 2022년 11월 18일 오전 12:23

문제 #12865. 평범한 배낭

여행에 필요하다고 생각하는 N개의 물건이 있다.

각 물건은 무게 W와 가치 V를 가진다. 해당 물건을 배낭에 넣어가면 준서가 V만큼 즐길 수 있다. 배낭은 최대 K만큼의 무게를 넣을 수 있다.

즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값 구하기

입력

1. N (1≤N≤100) : 물품 수 / K (1≤K≤100000) : 최대 무게
2. N개의 줄을 거쳐 각 무게의 W(1≤W≤1000000)와 물건 가치 V (0≤V≤1000)

4 7 # 물품 수 4, 최대 무게 7
6 13
4 8
3 6
5 12

출력

배당에 넣을 수 있는 물건들의 가치합의 최댓값

14

배경설명

한 가게에 도둑이 들었다. 도둑이 훔치고 싶은 물건들은 다 각각의 값어치(가치)와 무게가 있다. 무게 때문에 도둑은 고를 수 있는 물건이 한정되어 있다. 그러므로 가방에 담을 수 있는 내에서 가장 비싼 (가치가 높은) 물건을 훔치고자한다.

세 가지 방법이 있다.

1. 모든 경우의 수
   • 물건 개수 n개라면, 넣었는가, 넣지 않았는가 2가지의 경우가 있다.
   • $2^n$가지의 경우의 수를 구한다.
2. 넣을 수 있는 가장 비싼 물건부터 넣기
   • Greedy Algorithm
   • 최적의 해는 나오지 않는다. (뒤에서 예로 설명하겠다.)
3. 비밀 (동적 프로그래밍)

🎒냅색(Knapsack) 알고리즘

• 냅색 알고리이란? 유명한 DP 문제 중 하나 → 담을 수 있는 물건이 나눌 수 있냐 없느냐에 따라 2가지로 나뉜다.

  • Fraction Knapsack(분할가능 배낭문제) : 담을 수 있는 물건이 나누어질 때(ex. 설탕 몇 g등)
    → 물건의 가격을 무게로 나눔 → 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 문제 해결 가능!
    → 남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라 넣으면 됨)
    - greedy로 해결가능

  • 0-1 Knapsack (0-1 배낭문제) : 담을 수 있는 물건이 나누어질 수 없을 때(담는다 or 안담는다)
    → 물건을 자를 수 없음.
    → 물건, 물건의 무게, 물건의 가격(가치), 배낭의 남은 용량을 모두 고려해야 함
    - ⇒ dp로 해결가능

0-1 Knapsack

본 문제, #12865번은 물건을 자를 수 없으므로 0-1 Knapsacp에 해당

문제를 다시 리뷰해보면

• 담을 수 있는 무게는 K
• 물건의 무게W와 가치 V
• 가방에 최대로 담았을 때, 최대의 가치값을 구함

📌 이는 그리디 알고리즘과 비슷해보이지만 최적의 해가 나오지 않을 때도 있다.

ex) 가방에 7kg까지 담을 수 있고, 물건은 4가지가 있다. 이때 가치를 최대로 가지려면 어떤 물건을 담아야 하는가?

[물건 A] 무게 : 6kg, 가치 : 13
[물건 B] 무게 : 4kg, 가치 : 8
[물건 C] 무게 : 3kg, 가치 : 6
[물건 D] 무게 : 5kg, 가치 : 12
=>그리디 알고리즘
→ 가치를 최대로 갖도록 하면 그때그때 최선의 선택을 하기 때문에 물건 A를 고르고 끝낸다.

정답

→ 물건 A를 담지 않고, 물건B와 물건C를 담는다
⇒ 즉, 가장 가치가 높아 보이는 특정 물건을 담지 않았을 때에도 최적의 선택이 나옴
따라서, 이런 것까지 고려해주는 것이 냅색 알고리즘의 핵심

냅색알고리즘은 어떤 방법을 이용할까?

⇒ 동적프로그래밍 (dp)

📌 가방에 최대 K kg까지 물건을 담을 수 있고,
dp[i][j] = 가방에 담은 물건의 무게 합이 j일때, 처음 i개의 물건 중 담을 수 있는 최대 가치 (1 < j ≤ K )

1. j가 현재 물건 무게 W보다 작을 때
   • 현재 물건을 담을 수 없음 → 이전의 값 복사

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

2. j가 현재 물건의 무게 W와 같거나 클 때
   • 현재 물건 담을 수 있다.
   • 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤 더 큰 값을 할당한다.
   • 현재 물건의 가치는 V이다.

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

3. 따라서 물건의 최대 가치는 dp[가방크기][물건개수]로 구할 수 있다.

풀이과정

참고한 사이트 : [알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

1. 주어진 값 살펴보기

물건의 수는 4개이고 최대용량은 7이고, 물건의 정보가 다음 표와 같이 주어졌다.

	1번 물건	2번 물건	3번 물건	4번 물건
W(무게)	6	4	3	5
V(가치)	13	8	6	12

---

Knapsack	0	1	2	3	4	5	6	7
0
1
2
3
4

1. dp[i][j]

   dp[i][j]는 다음과 같이 정의된다.

dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j일때, 배낭에 들어간 물건의 가치합의 최댓값

→ 이 문제에서는 dp[N][K]가 들어간다.

• 1부터 N개의 모든 물건을 살펴본다.
• 배낭 용량이 K일때, 이 배낭에 들어가 있는 물건들의 가치 합의 최댓값이 들어가게 된다.

2. dp[i][j]에 대한 점화식 세우기

dp[i][j]값을 차례대로 채워가보자

dp[i][j]에는 dp[i-1][j]의 값과 dp[i-1][j-w[i]]+v[i]의 값 중 더 큰 값이 들어가게 된다.

즉,

• i번째 물건의 무게는 w[i]이고, 가치는 v[i]이다.
• 이제 i번째 물건을 배낭에 넣으려고 한다. 이때 배낭의 용량은 j이다.
• 용량이 j인 배낭에 i번째 물건을 넣지 않았을 때의 가치합의 최댓값은 dp[i-1][j]이다. 다시 말해, dp[i-1][j] 의 값은 배낭의 용량이 j였고, i-1번째 물건까지 살펴봤을 때의 가치합의 최댓값이다.
• 용량이 j인 배낭에 i번째 물건을 넣었을 때의 상황은 dp[i-1][j-w[i]]+v[i]가 된다.
  • 즉, i-1번째 물건까지 살펴보았고, 배낭의 용량이 j-w[i]였을 때의 값에 새롭게 i번쨰 물건을 넣은 상황이 되는 것이다.
• 예를 들어, dp[3][6]의 값을 구하는 상황일 때를 가정해보자
  • 용량이 6인 배낭에 i=3번째 물건을 넣지 않았을 때의 최댓값은 dp[2][6]에 저장된다.
  • 용량이 6인 배낭에 i=3번째 물건을 넣었을 때의 최댓값은 dp[2][6-w[3]]+v[3] =dp[2][3]+v[3]이다.
    • 최대 가치합으로 물건이 들어가 있는 용량이 3인 배낭에 i=3번째 물건(무게가 3)을 새롭게 넣는 상황.
    • dp에 저장되는 값은 가치의 합이므로 v[3]을 더해준다.

3. 메모이제이션

thing	0	1
i = 1	6	13
i = 2	4	8
i = 3	3	6
i = 4	5	12

---

Knapsack	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	6	8	8	12	13	14

⇒ 결과적으로 Kanpsack[n,k] 값이 출력값이 된다.

4. 구현하기

n, k = map(int, input().split()) # 물품의 수 n, 준서가 버틸 수 있는 무게 k

thing = [[0,0]]
knapsack = [[0]*(k+1) for _ in range(n+1)]

for i in range(n): 
    thing.append(list(map(int, input().split())))

for i in range(1, n+1):
		~~~~for j in range(1, k+1):
        w = thing[i][0]
        v = thing[i][1]

        if j - w >= 0: #  // i번째 물건을 넣을 수 있다면?
            knapsackd[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-w]+v)

        else: # // i번째 물건을 넣을 수 없다면, 배낭 용량은 같고 넣지 않았을 때의 값으로 초기화
            knapsack[i][j] = knapsack[i-1][j]

print(knapsack[n][k])

결론

• 동적계획법의 유명한 냅색 문제
• i번째 물건을 넣었을 때와 넣지 않았을 때, 둘 중 더 가치가 큰 것을 가져오면 됨
• 점화식 세우기!