평범한 배낭
문제 링크
틀린이유
- dp인 거까지는 찾았지만 dp에 확신이 없었다
- dp의 테이블을 정의해놓고 안되자 다른 테이블을 정의하려하지 않고 모르겠다 시전 (dp에 확신이 없었기 때문임)
문제 분석
문제
- N개의 물건 (각 물건은 무게 w와 가치 v를 가짐)
- 배낭에는 최대 K만큼의 무게만 넣을 수 있음
- 배낭에 넣을 수 있는 물건의 가치의 최댓값은?
입력
- 1 ≤ N ≤ 100
- 1 ≤ K ≤ 100,000
- 1 ≤ w ≤ 100,000
- 0 ≤ v ≤ 1,000
해결방안
조합으로 백트래킹하기에는 N이 크다 (백트래킹은 N ≤ 15 정도가 적당)
그리디로 하기에는 무게 또는 가치를 기준으로 해야하므로 맞지 않는다 (반례 생김)
그렇다면 DP인 것 같은데… 아니 DP다. 확신을 갖고 테이블 정의하자.
1. 테이블 정의
d[i] = 무게가 i일 때 가치합
위와 같이 테이블을 정의했을 때 물건을 넣었는지 안넣었는지 유무를 확인할 수가 없다. 2차원 배열로 선언해보자. 그럼 column을 물건 번호로 두고, row를 무게로 두면 되겠다..!
d[i][j] = i 번째 물건을 담을 차례, 무게가 j일 때 가치합
2. 점화식 찾기
column은 0~N까지, row는 0~K까지로 두고 예제 1에서 점화식을 찾아보자.
N = 4, K = 7
{{6, 13}, {4, 8}, {3, 6}, {5, 12}} // 각 물건의 무게와 가치를 담은 배열
w[i] ≤ k 일 때 배낭에 물건을 넣을 수 있다.
1) 물건을 넣을 수 있는 경우
i = 2, 무게가 4인 물건을 넣으려고 한다.
4 ≤ k 여야하므로 d[2][4]와 d[2][5] = 8로 채워졌다. d[2][6]과 d[2][7]에서는 최댓값 확인하는 작업이 필요하다. 왜냐하면 이미 무게가 꽉 채워진 것이므로 두 물건을 가져갈 수는 없다. 둘 중 하나만 가능하다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7(K) | |
|---|---|---|---|---|---|---|---|---|
| 0 | ||||||||
| 1 | 13 | 13 | ||||||
| 2 | 8 | 8 | ||||||
| 3 | ||||||||
| 4 (N) |
현재 물건을 선택했을 때와 현재 물건을 선택 안했을 때 두 경우가 있다.
현재 물건을 선택했을 때 : d[1]6-w[2]]+v[2]
현재 물건을 선택안했을 때 : d[1][6]
즉, max(d[i-1]k-w[i]] + v[i], d[i-1][k])를 하면 되겠다.
2) 물건을 넣을 수 없는 경우
물건을 넣을 수 없는 경우는 빈칸으로 남겨놔야할까? 아니다. d[i-1][k] 값을 그대로 가져오면 된다. 현재 물건을 선택 안했을 때와 똑같기 때문이다.
이제 점화식이 완성되었다.
if (w[i] <= j)
d[i][j] = max(d[i-1][j-w[i]] + v[i], d[i-1][j]);
else
d[i][j] = d[i-1][j];3. 초기값 찾기
배열 d의 초기값을 전부 0으로 하고, i와 j 모두 1부터 시작하면 된다.
4. 구하는 값
구하는 값은 N번까지 물건을 넣을지 말지 선택했고, 무게가 K일 때를 확인해보면 되겠네요. 즉, d[N][K]가 되겠죠?
전체 코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, K;
int d[102][100002];
int w[102];
int v[102];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i=1; i<=N; i++){
cin >> w[i];
cin >> v[i];
}
for (int i=1; i<=N; i++){
for (int j=1; j<=K; j++){
if (w[i] <= j) { // 담을 수 있음 (선택 가능)
d[i][j] = max(d[i-1][j], d[i-1][j-w[i]] + v[i]);
} else { // 담을 수 없음
d[i][j] = d[i-1][j];
}
}
}
cout << d[N][K];
return 0;
}