[12865번] 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

냅색(knapsack) 문제로도 유명한 다이나믹 문제입니다.

문제에서 배낭에 넣을 수 있는 무게 k가 주어지고, n개의 물건은 각각 무게 w와 가치 v가 주어집니다.
배낭 안에 물건을 이리저리 넣었을 때 담을 수 있는 물건의 최대가치값을 구하는 것입니다.
n개의 물건 각각은 배낭 안에 들어가거나 안 들어갈 수 있으며, 동일한 물건은 중복해서 넣을 수 없습니다.

 

다이나믹으로 문제를 해결할 때는 큰 문제는 작은 문제로 쪼갤 수 있기 때문에, 배낭에 넣을 수 있는 무게합 k 라는 값을 변수로 설정을 하고 1부터 k까지의 무게에서의 최대 가치값을 전부 구합니다.

또한 각각의 물건들도 넣을지 말지 고민을 해야하기 때문에 물건들과 배낭무게합을 이용하여 2차원 배열 점화식을 세워봅니다. 

 

점화식은 d[i][j] : i번째까지 물건을 넣을지 말지 판단을 했을 때, 배낭에 넣은 물건 무게의 합이 j일 때의 최대 가치값을 저장하는 2차원 배열입니다.
여기서 i번째 물건은 넣을 수도 있고, 안 넣을수도 있는데 두가지 경우에서 최대 가치값을 선택하면 됩니다.

 

1) i번째 물건을 안 넣는 경우 

d[i - 1][j]

d[i][j]가 i번째 물건을 안 넣은 것이라면, 그 이전의 무게와 변함이 없어지므로 j 무게는 동일하며 물건의 수는 1 줄어들었습니다. 물건을 넣지 않았으므로 가치값은 d[i - 1][j]와 d[i][j]는 같습니다.  

 

2) i번째 물건을 넣는 경우

d[i - 1][j - w[i]] + v[i]

d[i][j]가 i번째 물건을 넣은 것이라면, 바로 직전에 i번째 물건이 없는 경우를 생각해봅니다.

즉 물건의 수는 i - 1 가 되고, 무게는 j 에서 i번째 물건의 무게를 빼주어야 합니다. 그리고 나서 i 물건의 가치를 더해주면 그것이 i번째 물건을 넣는 가치값이 됩니다.

 

즉, d[i][j]에는 1)과 2)의 값 중 더 큰 값을 대입해주면 됩니다.

[코드1]

#include <iostream>
#include <algorithm>
using namespace std;
int d[101][100001];
int w[101]; //무게
int v[101]; //가치
int main () {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            d[i][j] = d[i - 1][j];
            if (j - w[i] >= 0) {
                d[i][j] = max(d[i][j], d[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    cout << d[n][k] << '\n';
    return 0;
}

[결과]

4 7 //input
6 13 //input
4 8 //input
3 6 //input
5 12 //input
14 //output

 

 

 

아래 코드는 1차원 배열로 풀이한 코드 입니다. 물건 정보를 점화식에서 아예 빼버리고 무게만을 가지고 점화식을 세운 것인데요.

여기서 점화식 d[i]의 의미는 물건 무게의 합이 i 일때 배낭에 넣을 수 있는 최대 가치값을 저장한다는 의미입니다.

 

[코드2]

#include <iostream>
#include <algorithm>
using namespace std;
int d[100001];
int w[101]; 
int v[101];
int main () {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = k; j >= 1; j--) { //반드시 j는 큰 쪽부터 채워야한다. 더보기란에 설명 참고
            if (j - w[i] >= 0) {
                d[j] = max(d[j], d[j - w[i]] + v[i]);
            }
        }
    }
    cout << d[k] << '\n';
    return 0;
}

[결과]

4 7 //input
6 13 //input
4 8 //input
3 6 //input
5 12 //input
14 //output

동일한 결과가 나오게 되지만 1차원 배열로 작성된 코드가 메모리와 실행속도는 훨씬 빠릅니다.

첫번째 줄은 1차원 배열로 푼 결과, 두번째 줄은 2차원 배열로 푼 결과

 

 

 

1차원 배열로 문제를 풀때는 주의해야 할 점이 있는데, 배열을 채워나갈 때 내부 for문에서의 j의 무게를 큰 쪽에서 작은 쪽으로 채워나가야 합니다.
왜냐하면 배낭무게합을 작은 쪽에서 큰 쪽으로 물건을 채우게 되면 동일한 물건을 중복해서 넣을 수 있기 때문입니다.

 

참고) 설명이 장황하여 참고하실 분만 보시라고 더보기로 접어둡니다.🙂

예를 들면, 하나의 물건을 여러가지 배낭 무게에 넣고 있는 중에, 현재 배낭 최대 무게합 k가 10, 물건 하나의 무게 w[i] = 5, 가치 v[i] = 3라고 합시다.

그러면 d[10]에는 현재 d[10]의 값과 d[10 - 5] + 3를 더한 값과 비교를 하게 됩니다. 

여기서 물건을 넣게 되는 경우의 가치가 더 클 경우 d[10]은 d[10 - 5] + 3의 값으로 대입됩니다.

그 다음에 for문에 의해 배낭 무게(k)가 증가하면서 동일한 물건을 계속 넣다가 배낭 무게(k)가 15인 것을 채워야 한다고 합시다.

그러면 d[15] 와 d[10] + 3을 비교하게 되고, d[10]에는 이전에 동일한 물건을 넣은 값이 계산되어 있겠지요.

또한 비교시 d[15] < d[10] + 3 이 되어서 d[10] + 3 값을 대입하게 되는 상황이 있을 수 있습니다. 그렇게 되면 동일한 물건을 또 넣어서 무게 15를 만들게 되므로 문제 조건을 위배합니다.

 

따라서 동일한 물건의 중복사용을 막기 위해 배낭 무게합을 큰 쪽에서부터 작은 쪽으로 채우게 하면 됩니다.

예를 들면, 배낭무게합을 15에서 시작한다고 할 때, d[15]와 d[10] + 3에서 물건을 담는 쪽이 가치가 더 커졌다면, d[15]에는 d[10]+ 3  값이 대입됩니다. 무게 15인 가방최대값을 만들기 위해 물품을 넣었습니다.

그리고 배낭 무게 합을 점점 줄여가며, 배낭 무게합 10을 채워야 한다고 했을 때, d[10]과 d[5] + 3을 비교하는 것인데, 둘 중에 무엇이 대입이 되든, 작은 배낭무게합은 더 작은 배낭무게합에서 계산되어서 채워지고 있습니다.

이전에 동일한 물건을 넣었던 현재 배낭 무게합보다 큰 배낭의 무게합 값들은 상관이 없어집니다.

즉, j를 큰 무게부터 채우게 되면 넣었던 물건을 절대로 중복해서 들어갈 수 없게 됩니다.