[백준 6066] Buying Hay

문제

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

 

알고리즘

Knapsack

 

풀이

갯수제한이 없는 01 Knapsack 문제입니다.

 

$cache[i][j]$ = $i$번째 물건까지 택하고 현재 얻은 hay양이 $j$ 일때 지불해야하는 최소 금액

 

으로 가정하면 풀 수 있습니다. $cache[i][j]$가 갱신하는 다음 상태는 현재 상태에서 hay를 구매했을때 상태인 $cache[i][j+hay]$ 와 현재 물건을 택하지 않고 다음 물건을 택하는 $cache[i+1][j]$가 있습니다. 

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, H;
int sup[105][2];
int cache[101][55100 + 5];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> H;
    rep(i, N) rep(j, 2) {
        cin >> sup[i][j];
    }
    int ans = INT_MAX;
    memset(cache, 0x3f, sizeof(cache));
    cache[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        int hay = sup[i][0];
        int cost = sup[i][1];
        for (int j = 0; j + hay <= 55000; ++j) {

            cache[i][j + hay] = min(cache[i][j + hay], cache[i][j] + cost);
            cache[i + 1][j] = min(cache[i + 1][j], cache[i][j]);
            if (j >= H) {
                ans = min(ans, cache[i][j]);
            }
        }
    }
    cout << ans;

    return 0;
}

 

갱신하는 상태가 $i$와 $i+1$인 점을 이용하여 다음과 같이 풀 수도 있습니다. 안쪽 포문의 순서를 작은 $j$부터 큰 $j$로 해서 여러개의 물건을 고르는 것을 고려할 수 있습니다.

코드2

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, H;
int sup[105][2];
int cache[55100 + 5];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> H;
    rep(i, N) rep(j, 2) {
        cin >> sup[i][j];
    }
    memset(cache, 0x3f, sizeof(cache));
    cache[0] = 0;
    rep(i, N) {
        for (int j = sup[i][0]; j <= 55005; ++j) {
            cache[j] = min(cache[j], cache[j - sup[i][0]] + sup[i][1]);
        }
    }
    int ans = INT_MAX;
    for (int i = H; i <= 55005; ++i) {
        ans = min(ans, cache[i]);
    }
    cout << ans;
    return 0;
}