https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
동적 프로그래밍으로 푸는 문제
무게가 저장된 배열 w[]와 값이 저장된 배열 v[]이 존재한다.
dp[i][j]를 i개 물건, 무게 j까지 담을 수 있는 가방에 담을 수 있는 물건의 총액의 최대값이라고 하자.
dp[i][j]의 값은 다음과 같다.
1. i==0 또는 j==0일 경우, 즉 담을 물건이 없거나 가방이 종이쪼가리일 경우
물건을 담을 수 없으므로 dp[i][j] = 0
2. w[i] <= j일 경우, 즉 해당 물건을 담을 수 있는 경우
이때 dp[i][j]의 값은 다시 두 가지로 나뉜다.
2-1. 담을 수 있는데.. 담는 경우
dp[i][j]는 i번째 물건을 넣기 전의 최대값에서 i번째 물건의 가치를 합한 값, 즉 dp[i-1][j-w[i]] + v[i]
2-2. 담을 수 있는데.. 안 담는 경우
i번째 물건이 가성비가 너무 구리다 싶어 안 담을 수도 있을 것이다.
이때 가방에 담긴 무게는 i-1번째 물건까지 확인했을 때와 동일하므로 dp[i][j] = dp[i-1][j]
따라서 dp[i][j]는 2-1)과 2-2)의 경우 중 더 큰 값이 된다.
3. w[i] > j여서 못 담는 경우
안 담으나 못 담으나 결과는 동일하므로 2-2와 마찬가지로 dp[i][j] = dp[i-1][j]
위의 값을 이용해 dp배열을 채우면 답을 구할 수 있다.
동적 프로그래밍은 '이게 되겠어?' 싶게 코드를 작성해도 답을 구해주는 신기한 재능을 가진거 같다
배운 내용
DP[i][j]는 구하고자 하는 문제 DP[N][K]의 축소판이므로, DP 배열의 정의를 문제와 동일하게 설정한다.
구하려는 값 dp[n][k] : 물품의 수 n, 버틸 수 있는 무게 k에 대해 배낭에 넣을 수 있는 물건들의 가치합의 최댓값
==> dp[i][j] : 물품의 수 i, 버틸 수 있는 무게 j에 대해 배낭에 넣을 수 있는 물건들의 가치합의 최댓값
'백준' 카테고리의 다른 글
| 백준 - 그리디 알고리즘 (0) | 2023.05.20 |
|---|---|
| 백준 4779 - 칸토어 집합 (0) | 2023.05.18 |
| 백준 9251 - LCS (0) | 2023.05.14 |
| 백준 2565 - 전깃줄 (0) | 2023.05.13 |
| 백준 11054 - 가장 긴 바이토닉 부분 수열 (0) | 2023.05.13 |