12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W와 해당 물건의 가치 V가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
제한
1 ≤ N ≤ 100
1 ≤ K, W ≤ 100,000
0 ≤ V ≤ 1,000
접근 방식
문제 이해
물품의 수: N / 버틸 수 있는 무게: K / 각 물건의 무게: W / 가치: V
물건은 < 넣거나, 넣지 않거나 > 2가지만 가능하다.
배낭에 넣을 수 있는 물건의 최대 가치는 얼마인가?
잘못된 접근
가방의 용량(버틸 수 있는 무게)에 따라 담을 수 있는 물건의 개수와 가치가 달라진다.
이는 즉, 용량에 따라 최적(최대)의 가치가 달라질 수 있다는 것이다.
우리는 담을 수 있는 모든 경우의 수 중에서 최대의 가치를 가지는 경우를 찾아야 한다.
이때, 물건을 무조건 많이 담는다고 가치가 가장 높은 것이 아니다.
n = 7, k = 10
3 1 / 3 2 / 4 10 / 1 1 / 1 1 / 2 4 / 2 1
물건을 5개 담을 때 → 3 1 / 3 2 / 1 1 / 1 1 / 2 4 = 총 가치 9
물건을 3개 담을 때 → 3 1 / 3 2 / 4 10 = 총 가치 13
물건의 개수가 더 적은데 가치는 높은 경우 존재
그렇다면 도대체 어떻게 구해야 할까. ..?
각 인덱스를 가방의 용량으로 가지는 dp 배열을 하나 두고 물건이 들어올 때마다 가치가 최대가 되도록 갱신하면 될까?
NOPE !!!
만약 n=3, k=5이고 물건의 정보가 <2, 2>, <3, 5>, <5, 1> 일 때, 크기가 6인 dp 배열로 문제를 해결한다고 가정하자.
capacity = index 이다.
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| value | 0 | 0 | 0 | 0 | 0 | 0 |
1. w=2, v=2
a. capacity가 w=2보다 작을 경우
가방에 현재 물건을 담을 수 없다. 가치는 여전히 0이다.
b. capacity가 2보다 크거나 같은 경우
가방에 물건을 담았다. 가치가 갱신된다.
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| value | 0 | 0 | 2 | 2 | 2 | 2 |
2. w=3, v=5
a. capacity가 w=3보다 작을 경우
가방에 현재 물건을 담을 수 없다. 가치는 이 물건을 담기 전의 가치와 동일하다.
-> 이전의 물건을 통해 갱신한 값
b. capacity가 2보다 크거나 같은 경우
가방이 현재 물건을 버틸 수 있다. 하지만, 가방에 현재 물건을 담을 수도 담지 않을 수도 있다.
현재 물건을 담지 않고 기존 물건만 담을 때, 가치가 더 높을 수 있다.
-> 2 vs 5 에서 5가 이긴다.
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| value | 0 | 0 | 2 | 5 | 5 | 5 |
3. w=5, v=1
a. capacity가 w=3보다 작을 경우
가방에 현재 물건을 담을 수 없다.
가치는 이 물건을 담기 전의 가치와 동일하다.
-> 이전의 물건을 통해 갱신한 값
b. capacity가 2보다 크거나 같은 경우
가방이 현재 물건을 버틸 수 있다. 하지만, 가방에 현재 물건을 담을 수도 담지 않을 수도 있다.
현재 물건을 담지 않고 기존 물건만 담을 때, 가치가 더 높을 수 있다.
-> 2 vs 1 또는 5 vs 1 에서 전부 지므로 원래 값 유지
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| value | 0 | 0 | 2 | 5 | 5 | 5 |
헉. 뭔가 이상한데….? 가방이 담을 수 있는 무게가 5일 경우에…
무게가 2, 가치 2인 물건이랑 무게 3, 가치 5인 물건을 둘 다 담은 경우에 제일 좋은 거 아니야??!? 😱😱😱😱
옳은 접근
문제 이해 부분을 다시 보자.
물건을 담을 수도 있고, 담지 않을 수도 있고. 이게 무슨 의미일까?
내가 가치가 높더라도 다른 물건들을 담았을 때 가치가 더 높다면 그게 맞는 것이다!
물건을 두 개 이상 담을 수 있기 때문에, 가방이 수용할 수 있는 무게에 대하여 물건 여러개를 담았을 때의 가치 합이 더 높다면 그게 답이 된다.
가방의 용량이 5일 때, 무게 2의 물건이 들어왔다고 하자.
무게 2의 물건을 넣었을 때의 가치와, 넣고 남은 용량 3이 수용할 수 있는 가치의 합
vs
현재 물건을 넣지 않고 다른 물건들을 넣었을 때의 최대 가치
따라서, 우리는 (N+1) x (K+1) 크기의 배열을 사용한다.
그리고 정답은 dp[N+1][K+1]의 값이 된다.
즉, 물건 하나당 가방의 용량을 최솟값(1)부터 최댓값(K+1)까지의 가치를 한 번씩 계산하면서 그 값을 최적화해 가는 것이다.
동일한 예시(n=3, k=5이고 물건의 정보가 <2, 2>, <3, 5>, <5, 1>)로 예를 들어보자.
전체적인 과정은 위와 유사하지만 조금씩 다른 부분이 핵심이 되므로, 꼼꼼히 보자.
1. w=2, v=2
첫 번째는 위에서의 과정과 동일하다.
a. capacity가 w=2보다 작을 경우
가치는 여전히 0이다.
b. capacity가 2보다 크거나 같은 경우
가방에 물건을 담았다. 가치가 갱신된다.
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| max value | 0 | 0 | 0 | 0 | 0 | 0 |
| w=2, v=2 | 0 | 0 | 2 | 2 | 2 | 2 |
2. w=3, v=5 (중요한 예시)
a. capacity가 w=2보다 작을 경우
가능한 최대 가치는 이 물건을 담기 전의 최대 가치와 동일하다.
-> 이전의 물건을 통해 갱신한 값 = dp[thing-1][capacity]
b. capacity가 2보다 크거나 같은 경우
가방에 현재 물건을 담을 수도 담지 않을 수도 있다.
1. 담지 않을 때
이전의 물건을 통해 갱신한 값
= dp[thing-1][capacity]
2. 담을 때
가방의 용량(capacity)에서 현재 물건의 무게(w)를 뺀 나머지의 용량(capacity-w)이 수용할 수 있는 최대 가치 + 현재 물건의 가치(v)
= dp[thing-1][cap-w] + v
3. 담지 않을 때와 담을 때의 가치 값을 비교하여 큰 값을 dp 배열에 저장한다.
capacity = 5 일 때
a. capacity < w 이므로 조건 만족 X
b. capacity ≤ w 이므로 수행
1. 담지 않을 때: dp[thing-1][capacity] = dp[1][5] = 2
2. 담을 때 : dp[thing-1][capacity-w] + v = dp[1][2] + 5 = 2 + 5 = 7
3. 비교: max(1, 2) = max(2, 7) = 7
결론: 현재 물건을 담는다. (단, 1번 물건과 함께 담는다.)
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| max value | 0 | 0 | 0 | 0 | 0 | 0 |
| w=2, v=2 | 0 | 0 | 2 | 2 | 2 | 2 |
| w=3, v=5 | 0 | 0 | 2 | 5 | 5 | 7 |
3. w=5, v=1
a. capacity가 w=5보다 작을 경우
이 물건을 담기 전의 최대 가치
b. capacity가 2보다 크거나 같은 경우
1. 담지 않을 때의 가치 계산
2. 담을 때의 가치 계산
3. 담지 않을 때와 담을 때의 가치 값을 비교하여 큰 값을 dp 배열에 저장한다.
| capacity | 0 | 1 | 2 | 3 | 4 | 5 |
| max value | 0 | 0 | 0 | 0 | 0 | 0 |
| w=2, v=2 | 0 | 0 | 2 | 2 | 2 | 2 |
| w=3, v=5 | 0 | 0 | 2 | 5 | 5 | 7 |
| w=5, v=1 | 0 | 0 | 2 | 5 | 5 | 7 |
답: dp[N+1][K+1] = dp[4][6] = 7
알고리즘
thing: 몇 번째 물건인가(1 ≤ thing ≤ N), capacity: 가방의 용량(1 ≤ capacity ≤ K),
w = 현재 물건의 무게, v = 현재 물건의 가치라고 할 때, dp[thing][capacity] 구하기
점화식
- 가방의 용량이 현재 물건을 수용할 수 없을 때
- 현재 물건을 넣지 않고 가방의 용량에 최대 가치를 저장한 dp[thing-1][capacity]를 dp 배열에 그대로 저장한다.
- dp[thing][capacity] = dp[thing-1][capacity]
- 가방의 용량이 현재 물건을 수용할 수 있을 때
- 현재의 물건을 가방에 넣을 경우와 넣지 않을 경우에 대하여 가능한 가치 값 중 최댓값을 dp 배열에 저장
- dp[thing][capacity] = max(dp[thing-1][cap-w] + v, dp[thing-1][capacity])
시간 복잡도
각 물건마다, 1부터 배낭의 최대 용량까지 탐색
N * K * O(1) → O(NK)
제출
맞았습니다!!
Code
코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
int w, v;
int dp[n+1][k+1];
for (int i=0; i<=k; i++) dp[0][i] = 0;
for (int i=0; i<=n; i++) dp[i][0] = 0;
for (int thing=1; thing<=n; thing++){
cin >> w >> v;
for (int cap=1; cap<=k; cap++){
if (w >
cap) dp[thing][cap] = dp[thing-1][cap];
else{
int temp=0;
if(k-cap>=0 && cap-w>0) temp = dp[thing-1][cap-w];
dp[thing][cap] = max(dp[thing-1][cap], temp + v);
}
}
}
cout << dp[n][k];
}
