문제 이해 단계
N개의 물건이 주어지고 각 물건에는 무게(W)와 가치(V)가 주어진다.
최대 K만큼 들 수 있을 때, 가질 수 있는 가치의 최댓값을 구하는 문제
문제 접근 단계
이 알고리즘의 문제는 이름에서 유추해 볼 수 있듯이
배낭 알고리즘이라는 DP 알고리즘 기법 쪽에서는 좀 유명한? 그런 알고리즘이다.
우선 여기서 주어지는 변수는 무게(W), 가치(V) 총 2가지가 있다.
이 두 가지 값은 모두 변하는 값이고, 가치의 최댓값을 구하는 데에 분명 영향을 줄 것이다.
즉, 점화식은 W, V를 이용한 2차원배열로 만들어질 가능성이 높다.
이제 이 점을 유의하면서 예제를 가지고 생각해 보자!!
| 무게 | 가치 |
| 6 | 13 |
| 4 | 8 |
| 3 | 6 |
| 5 | 12 |
이를 위에서 아래로 순차적으로 탐색한다고 가정한다.
그러니까 무게 순으로 6,4,3,5으로 한다는 뜻이다.
해당 물건을 배낭에 넣느냐 안 넣느냐, 이 두 가지 선택이 있을 텐데,
무슨 판단으로 넣느냐가 중요하다.
해당 가방의 무게가 현재 내가 버틸 수 있는 무게보다 무거우면, 배낭에 넣을 수 없다.
즉 해당 물건의 무게 W가 현재의 K보다 작으면 배낭에 넣을 수 없다.
이보다 가벼우면 일단 1차 관문은 통과하는 셈이다.
2차적으로 판단해야 할 것은,
해당 물건을 배낭에 넣었을 때의 가치의 합이 이전의 최대 가치합보다 높은가?
이 말이 무슨 말이냐면, 우리가 구해야 하는 것은 가치의 최댓값이다.
즉, 해당 물건을 넣었을 때의 가치합이 이전 최댓값보다 작다면 해당 값은 필요 없다는 뜻이 된다.
이 2가 지점으로 우리는 점화식을 세울 수 있다.
DP [A][B] = C : 순차적으로 물건 A까지 진행했을 때, 무게 B일 때의 최대 가치는 C이다.
라고 가정한다.
해당 가방의 무게가 현재 내가 버틸 수 있는 무게보다 무거우면 배낭에 넣을 수 없다.
이 부분을 DP를 이용하여 점화식을 세우려고 하는데 필요한 정보가 있다.
바로 '현재 내가 버틸 수 있는 무게'인데, 이를 하나하나 구하자니
너무 많은 경우에 수가 있어 구하기가 어렵다.
그래서 DP [A][B]에서 B부분을 그냥 반복문을 사용하여 1~K까지 반복하기로 하였다.
이를 이용하면 '현재 내가 버틸 수 있는 무게'는 해결 1차에 관련된 점화식을 세워보자.
if(weight [i] <=j)
해당 물건을 배낭에 넣었을 때의 가치의 합이 이전의 최대 가치합보다 높은가?
이런 식이 될 것이다.
여기서 weight [i]는 각 물건의 무게 값을 뜻하고 j는 1~K까지 반복되는 B부분이다.
해당 물건을 배낭에 넣었을 때의 가치의 합이 이전의 최대 가치합보다 높은가?
이 부분을 점화식으로 만들어보자.
먼저 '이전의 최대 가치합'이다.
이전의 최대 가치합이란 뜻은, 현재 물건을 사용하지 않았을 때의 가치합이므로
이는 DP [i-1][j]이다.
왜냐하면 순차적으로 탐색했기 때문에 i번째 이전에는 i-1번째를 탐색했을 것이고
물건을 배낭에 넣지 않았어도 이미 j번째 무게이기 때문이다.
두 번째로 해당 물건을 넣었을 때의 가치의 합이다.
결론부터 말하면 DP [i-1][j-weight [i]]+value [i]이다.
해당 물건을 넣었다는 것은 사전에 이 물건을 넣을 만한 무게가 있었다는 의미이다.
그렇기 때문에 j에서 그만큼의 무게를 비워주기 위해weight [i]만큼을 빼줘야 한다.
그리고 그때의 최대 가치의 합과 더해준다.
그리고 해당 물건의 가치만큼 더해준다.
이 두 값을 비교해서 더 큰 값이 해당 DP [i][j]의 가치값이 된다.
이제 이를 코드로 구현하면 답이 된다.
문제 구현 단계
#include <iostream>
using namespace std;
int weight[101];
int value[101];
int d[101][100001];
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,K;
cin >> N >> K;
for(int i = 1; i<=N; i++){
cin >> weight[i];
cin >> value[i];
}
for(int i = 1; i <= N; i++){
for(int j = 1; j<= K; j++){
if(j >= weight[i]) d[i][j] = max(d[i-1][j],d[i-1][j-weight[i]]+value[i]);
else d[i][j] = d[i-1][j];
}
}
cout << d[N][K];
}설명에 비해 코드는 굉장히 간결하게 나온다.
이중 반복문에서 바깥 반복문은 물건들을 뜻하고, 내부 반복문은 무게를 뜻한다.
위에서 설명했듯이 해당 무게가 j값 이내, 즉 감당 가능한 무게라면 비교를 하여
더 큰 값을 해당 dp값을 사용한다.
그렇지 않다면 이전 DP의 최댓값을 자동으로 해당 dp의 값으로 사용한다.
시행착오
알고리즘에서는 유명한 배낭 알고리즘 문제를 처음 접해봤다.
답지를 보지 않은 상태로 한번 풀어보려고 덤벼봤는데 역시 쉽지 않았다.
처음에는 접근에 성공해서 풀이에 성공한 줄 알았는데,
틀렸습니다가 계속 뜨다가 결국에는 예외케이스를 발견해서
이 예외케이스를 해결하지 못해서 인터넷을 찾아봤다.
신박하기도 하고 내가 생각 못할만한 알고리즘이었다.
이해하는데 꽤 걸렸고 아직도 약간 갈팡질팡하다.
좀 더 연습해서 내 걸로 만들어야겠다.
배낭 알고리즘 문제는 변형도 꽤 있으니까
조만간 이론으로 블로그 따로 정리해 둬야겠다.