(c++) BOJ 12865번: 평범한 배낭

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

12865번: 평범한 배낭

 

 

---

 

 

문제 개요

 

 

동적 계획법에서 유명한 문제인 배낭 문제이다.

 

일반적으로 푼다면 전체 2^n 의 경우의 수가 나오는데  

 

물품을 가져갈지, 가져가지 않을지 두 가지 중에서 가치합이 큰 경우를 골라주는 알고리즘을 구현하면 된다.

 

물품을 가져가지 않을 경우

pack(남은 용량, 물품 수 +1)

 

물품을 가져가는 경우

pack(남은 용량 - 선택 물품의 용량, 물품 수 +1) + 가치 v값  

 

이 경우를 저장하여 메모이제이션을 이용해 주면 된다.

 

max(물품을 가져가지 않을 경우, 물품을 가져가는 경우 + 물품의 가치)

 

 

코드

 

 

함수의 시작은 최대 용량인 k와 물품이 0개부터 시작하기에 pack(k, 0)으로 해주면 된다.

 

최대 물품 용량이나 가치의 합이 int형의 크기를 넘지 않기에 따로 생각하지 않아도 된다.

 

#include <bits/stdc++.h>

using namespace std;

int n, k;
int volume[100], need[100];
int cache[100001][100];
// capacity 남은 용량, item 물품 수
int pack(int capacity, int item) {
    // 물품을 다 넣을 경우
    if (item == n) return 0;
    int& ret = cache[capacity][item];
    if (ret != -1) return ret;
    // 물품 안 넣는 경우
    ret = pack(capacity, item+1);
    // 물품 넣을 경우 (남은 용량이 크거나 같을 때)
    if (capacity >= volume[item]) {
        ret = max(ret, pack(capacity-volume[item], item+1) + 
                need[item]);
    }
    return ret;
}
int main(void) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> volume[i] >> need[i];
    }
    // fill [행 크기 최대-1][열 크기 최대]
    fill(&cache[0][0], &cache[100000][100], -1);
    cout << pack(k, 0);
}