백준 1106 호텔 (C++)

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

Cost, Value가 정해져 있는 다이나믹 프로그래밍 배낭문제이다.

다만 이 문제는 평범한 배낭문제와 달리 중복을 허용한다. 그래서 이 문제는 일반적인 배낭 문제의 변형이다.

 

일반적인 식은 다음과 같다.

for(int i = 1; i <= M; i++){
        int cost = item[i - 1].first;
        int value = item[i - 1].second;

        for(int j = 1; j < 100001; j++){
            if(j >= cost){
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost] + value);
            } else{
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

 

i번의 행을 만들 때는 i - 1번 행을 보고 표를 갱신하게 된다. 그래서 i - 1행에는 당연히 이번 아이템이 없을태니 중복이 아닌 것이 보장된다.

if j >= cost 

일 때를 보면 i 번째 행은 모두 i - 1 둘중한 경우에서 갱신된다. 그렇다면 이번 아이템을 허용 가능하기 위해선 만약 이 아이템을 더했을 갱신 때 , i -1 이 아닌 바로 뒤 i에서 갱신되게 하면 된다.

 

for(int i = 1; i <= M; i++){
        int cost = item[i - 1].first;
        int value = item[i - 1].second;

        for(int j = 1; j < 100001; j++){
            if(j >= cost){
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost] + value); // 변경
            } else{
                dp[i][j] = dp[i - 1][j];
            }

            if(dp[i][j] >= N){
                answer = min(answer, j);
            }
        }
    }

 

이렇게 하면 중복을 허용한 것이 된다.

 

그런데 이 문제를 풀고 난 후 검색을 해보니 1차원 배낭으로 만든 분들이 대부분이었다.

위에서 말했던, 중복이 해결되기 위해 i - 1이 아닌 같은 행에서 처리하기 때문에 이전의 행을 남겨둘 필요가 없다. 

 

#include<iostream>
#include<vector>
using namespace std;

int dp[21][100001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M; cin >> N >> M;

    vector<pair<int, int>> item;

    for(int i = 0; i < M; i++){
        int a, b; cin >> a >> b;
        item.push_back({a, b});
    } 

    for(int i = 0; i < 21; i++)
        for(int j = 0; j < 100001; j++)
            dp[i][j] = 0;

    int answer = 1000000000;
    for(int i = 1; i <= M; i++){
        int cost = item[i - 1].first;
        int value = item[i - 1].second;

        for(int j = 1; j < 100001; j++){
            if(j >= cost){
                dp[i][j] = max(dp[i - 1][j], dp[i][j - cost] + value);
            } else{
                dp[i][j] = dp[i - 1][j];
            }

            if(dp[i][j] >= N){
                answer = min(answer, j);
            }
        }
    }
    cout << answer << '\n';
}