[백준 12865번] 평범한 배낭 (C++)

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

12865번: 평범한 배낭

---

평범한 배낭 문제에서 가치가 높은 물건부터 선택하면 최대 가치를 만들 수 있는가?

아닙니다. 아래의 예시를 보면, 무게가 1000인 물건을 먼저 넣으면 가치를 최대로 만들 수 없습니다.

7 1000
1000 10 
500 1
100 9
100 8
90 8
80 6
70 4

평범한 배낭 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

테이블 d[i]는 배낭에 넣을 수 있는 무게가 i일 때, 가치의 최댓값을 나타냅니다.

무게가 w[i]인 i번째 물건을 무게가 j(0 ≤ j ≤ k)인 배낭에 넣어보고, 무게가 j + w[i]인 배낭도 가치가 커지는 지 확인해보면 됩니다.

 

아래 테스트 케이스로 예를 들어보겠습니다. 

4 7
6 13
4 8
3 6
5 12

아래는 d[i], temp[i]는 초기 상태입니다. 

temp[i]는 d[i]의 변경사항을 일괄 적용시키기 위한 배열입니다.

물건 번호	무게	가치
1	6	13

	0 (무게)	1	2	3	4	5	6	7
d[i]	0 (가치)	0	0	0	0	0	0	0
temp[i]	0 (가치)	0	0	0	0	0	0	0

 

현재, d[0], d[1]은 0입니다.

이 배낭에 첫번째 물건을 넣으면 temp[0 + 6] = max(0, 13) = 13, temp[1 + 6] = max(0, 13) = 13이 됩니다.

 

첫번째 물건을 넣을 수 있는 배낭을 모두 갱신 시켜주었으므로, temp를 d[i]에 기록해줍니다.

	0 (무게)	1	2	3	4	5	6	7
d[i]	0 (가치)	0	0	0	0	0	13	13
temp[i]	0 (가치)	0	0	0	0	0	13	13

 

물건 번호	무게	가치
2	4	8

현재, d[0], d[1]은 0입니다.

이 배낭들에 두번째 물건을 넣으면 temp[0 + 4] = max(0, 8) = 8이 되고, temp[1 + 4] = max(0, 8) = 8이 됩니다.

 

현재, d[2], d[3]은 0입니다. 

이 배낭들에 두번째 물건을 넣으면 temp[2 + 4] = max(13, 8) = 13, temp[3 + 4] = max(13, 8) = 13이 됩니다.

두번째 물건을 넣을 수 있는 배낭을 모두 갱신 시켜주었으므로, temp를 d[i]에 기록해줍니다.

	0 (무게)	1	2	3	4	5	6	7
d[i]	0 (가치)	0	0	0	8	8	13	13
temp[i]	0 (가치)	0	0	0	8	8	13	13

 

이와 같은 방법으로 모든 물건에 대해 반복해주면 아래와 같은 테이블을 얻을 수 있습니다.

즉, 무게가 k일 때, 최대 가치 d[k] = 14를 얻을 수 있습니다. 

	0 (무게)	1	2	3	4	5	6	7
d[i]	0 (가치)	0	0	6	8	8	13	14
temp[i]	0 (가치)	0	0	0	0	0	0	0

 

이차원 배열로 해결하는 방법보다 메모리를 더 적게 사용하여 풀 수 있습니다. 

 

아래는 전체 코드입니다. 

#include <bits/stdc++.h>
using namespace std;
 
int w[101], v[101];
int d[100010], temp[100010];  // d[i]는 무게가 i일 때, 배낭에 넣을 수 있는 가치의 최댓값
int n, k; 
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k;  // n, k 입력 받음
    for(int i = 1 ; i <= n; i++) cin >> w[i] >> v[i]; // 무게와 가치 입력 받음
 
    for(int i = 1; i <= n; i++){ // i는 물건의 번호를 나타냄 (1 ~ n)
        memcpy(temp, d, sizeof(temp));
 
        for(int j = 0; j <= k; j++){    // j는 무게를 나타냄
            // i번째 물건을 무게가 j(0 ≤ j ≤ k)인 배낭에 넣어보고, 무게가 j + w[i]인 배낭도 가치가 최대가 되는지 확인
            if(j + w[i] <= k)   // 무게가 j인 배낭에 무게가 w[i]인 물건을 넣어도 k보다 무게가 많이 나가지 않는 경우
                temp[j + w[i]] = max(temp[j + w[i]], d[j] + v[i]);  
        }
        for(int j = 0; j <= k; j++) d[j] = temp[j]; // d[i] 갱신
    }
 
    cout << d[k];
}

아래는 문제 풀이에 사용된 테스트케이스입니다.

7 100
7 4
8 6
9 8
10 8
10 9
50 1
100 10
-> 36