BOJ 12865 - 평범한 배낭(dp, knapsack)

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

12865번: 평범한 배낭

- 가방에 넣는 물품의 갯수가 최대 100개여서 dfs로 풀면 넣고 안넣고의 경우의 수가 2^100 이기 때문에 O(N^2)가 아닌 다른 방식으로 풀어야한다. 이런 경우 greedy 방식이나 dp 메모이제이션 방식을 고민해볼 수 있다. 조건에서 가방의 제한무게가 10만이하로 주어졌기 때문에 d[i][j] = max(i번째 물건까지 고려해서, 넣은 무게 합이 j인 경우의 총 가치) 로 정의하여 순차적으로 구해나갈 수 있다.

- 바텀업 방식, 탑다운 방식

#include <iostream>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int n, k;  // 물건갯수100, 최대무게10만 // O(N^2)미만으로 풀어야됨
int w[101], v[101];
int d[101][100001];
// d[i][j] = max(i번째 물건까지 고려해서, 넣은 무게 합이 j)
// d[i-1][j] : i 안 넣은경우
// d[i-1][j -w[i]] + v[i] : i 넣은 경우
// -> O(NK)
int main() {
    FASTIO;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            d[i][j] = d[i - 1][j];
            int rest = j - w[i];
            if (rest >= 0) {
                d[i][j] = max(d[i][j], d[i - 1][rest] + v[i]);
            }
        }
    }
    // 각각의 무게에 대해서 넣을 수 있는 가장 큰 가치
    int ans = -1;
    for (int j = 1; j <= k; ++j) {
        ans = max(ans, d[n][j]);
    }
    cout << ans;
    return 0;
}

#include <algorithm>
#include <iostream>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int n, k;  // 물품100, 무게10만
int w[101], v[101];
int d[103][100003];

int go(int i, int totW) {
    if (i > n) return 0;
    if (d[i][totW]) return d[i][totW];

    int ans = 0;

    if (w[i] + totW <= k) {
        ans = go(i + 1, w[i] + totW) + v[i];
    }
    ans = max(ans, go(i + 1, totW));
    return d[i][totW] = ans;
}

int main() {
    FASTIO;

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }

    cout << go(1, 0);
    return 0;
}