12865 평범한 배낭
DP 문제의 가장 기초적인 문제
배낭문제로 알려져있음
분할 가능한 배낭 문제와, 0/1 배낭 문제로 나뉘는데
분할 가능한 배낭 문제는 그리디 알고리즘으로 해결 가능하지만,
0/1 배낭 문제는 동적 계획법이 필요
https://www.acmicpc.net/problem/12865
1. 문제
간단 설명
물품의 수와 가방의 무게가 주어지고
물건들의 무게와 가치가 쭉 주어짐
가방에 담을 수 있는 가치의 최대값을 출력하는 문제
즉 가방에 최대한 비싼거 많이 들고 튀어야함
2. 문제 분석
필요변수
물품의 수 int N, 가방의 무게 int K
물건들의 무게 리스트 int weight 배열
물건들의 가치 리스트 int value 배열
그리고 가장 중요한 DP2차원 배열
알고리즘
동적 계획법, 다이나믹 프로그래밍에서는 점화식을 세우는 것이 최대 관건이다
이 문제에서는
i열은 넣을 수 있는 물건을 의미한다
- 첫번째 물건만 있는 경우
- 첫번째, 두번째 물건만 있는 경우
- …
- 1~N개의 물건이 있는 경우 확장해 나간다. 0번째 열은 아이템이 없는 경우이므로 가치가 모두 0이다
j열은 가방의 무게를 의미한다
- 가방의 무게가 1인 경우
- 가방의 무게가 2인 경우
- …
- 가방의 무게가 K인 경우 로 확장해 나간다
여기서부터 표를 채워 나간다
1번 열
- 1번열의 첫번째 칸 : 1번 아이템을 가방 사이즈 1인 가방에 넣어본다 => 안들어감. 전체 가방 가치 0
- (1,2) : 1번 아이템, 가방 사이즈 2 => 마찬가지로 안들어감
- …
- (1,6) : 1번 아이템을, 가방사이즈 6인 가방에 넣어봄 => 들어감! 전체 가방 가치 13
- (1,7) : 1번 아이템, 사이즈 7 가방 => 마찬가지로 들어감. 전체 가방 가치 13
이렇게 첫번째 열이 완성되었다
2번 열
1번 물건과 2번 물건을 손에 들고있고, 가방에 우겨넣어본다
- 1번 열과 마찬가지로 진행한다.
가방 사이즈가 1번이나, 2번 물건의 크기보다 작을때는 넣지 못하지만,
가방사이즈 4일때는 2번 물건을 넣을 수 있다
가방사이즈가 6인 경우 1번을 넣을지, 2번을 넣을지 고민해본다.
당연히 가치가 13으로 더 높은 1번 물건을 넣는게 이득이므로 13을 적는다.
3번 열
- 1, 2, 3번 물건이 손에 있는 경우, 가방에 넣어본다
- 가방 사이즈가 3일때, 3번 물건을 넣을 수 있으므로 넣어본다.
- 가방 사이즈가 4일때, 2번 물건과 3번 물건 중 가치가 더 나가는걸 비교한다
- 가방사이즈가 6일 때, 2번 물건 vs 1번 물건 중 가치가 더 나가는걸 넣는다.
- 손에 1,2,3번 물건이 있고, 가방사이즈가 7일 때를 생각해본다
- 이전에 가방 사이즈가 7일때 1번 물건을 넣었을 경우 가치가 13인걸 기억해냈다
또한, 가방 사이즈가 4일때, 2번 물건을 넣었을 경우 가치가 8이였던걸 기억해냈고,
여기에 3번 물건을 넣어보려 시도해본다. => 들어감!
전체 가방 가치는 14로, 가방 사이즈가 7일때, 1번 물건을 넣었던 때보다 더 가치가 높으므로
14를 기록한다
4번 열
- 1, 2, 3, 4번 물건이 손에 있고, 가방에 넣는 경우
- j 가 4까지는 가방에 안들어가므로, 윗열의 기록을 가져온다.
- j==5일때, 가방에 4번 물건을 넣어보거나, 이전의 3번 물건을 넣은 기록을 비교한다
- j==6 도 마찬가지
- j==7 도 마찬가지.
이런식으로 표가 모두 완성되었다
(4, 7)의 셀은
손에 1,2,3,4 물건이 있을 때,
가방 사이즈가 7일때 넣을 수 있는 최대의 가치를 의미한다
즉, 우리가 원하는 최대값이므로 이를 출력하면 끝
점화식
N번 물건을 넣어보려할 때,
- 가방 사이즈(j)가 물건의 무게보다 작은 경우(W[N])
- 안들어가므로, 윗열의 물건 넣었던 기록([N-1][j])을 그대로 가져온다.
그거라도 챙기는게 이득이므로
- 가방에 현재 물건을 담을 수 있는 경우 1) 윗열의 물건 넣었던 기록([N-1][j])을 그대로 가져오기 2) 윗 열에서 현재 무게만큼 뺀 곳의 값([N-1][j - weight[i]]) + 현재 아이템의 가치(value[i])
- 1)과 2)의 값을 비교하여 더 큰값을 챙긴다
3. 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
int N, K;
int weight[MAX];
int value[MAX];
int DP[101][MAX]; //
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> weight[i] >> value[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
// 가방의 무게(j)가 현재 아이템의 무게보다 작다면, 가방에 들어가지 않음
if (j < weight[i]) {
// 윗열의 값을 그대로 가져온다
DP[i][j] = DP[i - 1][j];
}
// 가방에 물건을 담을 수 있는경우
else {
// 윗 열의 값을 그대로 가져오기 vs 윗열에서 현재 무게만큼 뺀 곳의 값 + 현재 아이템의 가치
// 두개를 비교해서 큰 값을 DP[i][j]에 담는다
DP[i][j] = max(DP[i - 1][j - weight[i]] + value[i], DP[i - 1][j]);
}
}
}
printf("%d", DP[N][K]);
/*
DP[i][j]
i : 물건의 번호까지 아이템을 넣을수 있음. 1은 1만, 2는 1,2. 3은 1,2,3개 선택 가능
j : 배낭의 무게
w v
6 13
4 8
3 6
5 12
i/j 1 2 3 4 5 6 7
1 0 0 0 0 0 13 13
2 0 0 0 8 8 13 13
3 0 0 6 8 8 13 14
4 0 0 6 8 12 13 14
if(j < w[i]){
T[i][j] = T[i-1][j] // 비교할 수 있는 대상이 없으므로 위의 값 그대로 가져오기
}
else{
T[i][j] = max{ T[i-1][j - w[i]]
T[i-1][j]
}
*/
return 0;
}
참고 : 1. https://www.youtube.com/watch?v=8LusJS5-AGo&ab_channel=TusharRoy-CodingMadeSimple 2. https://www.youtube.com/watch?v=cJ21moQpofY&t=665s&ab_channel=WilliamFiset
인도 형님이 오늘도 날 구했다