[백준 12865] 평범한 배낭

문제

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

알고리즘

knapsack

풀이

갯수제한이 있는 01 knapsack 문제입니다.

$cache[i]$=현재 담은 무게가 $i$ 일때 얻을 수 있는 최대가치

안쪽 포문을 역순으로 고려하면 갯수를 하나 택할 때 상황만을 고려할 수 있습니다.

코드

#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, K;
int bag[100][2];
int cache[100005];
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 >> K;
    rep(i, N) rep(j, 2) cin >> bag[i][j];

    rep(i, N) {
        for (int j = K; j >= bag[i][0]; --j) {
            cache[j] = max(cache[j], cache[j - bag[i][0]] + bag[i][1]);
        }
    }
    cout << cache[K];
    return 0;
}