[백준] 2662 기업투자

문제 링크

http://icpc.me/2662

2662번: 기업투자

풀이

배낭 문제라고도 불리는 웰노운인 knapsack문제다. 

dp를 이용하여 풀 수 있다.

dp[i][j] = max(dp[i - 1][j - k] + arr[k][i]) (0 <= j <= n, 0 <= k <= j)

=> i번째 기업까지만 골랐을때 i번째 기업에 k만큼 투자했고, 총 j만큼 투자했다.

위의 점화식으로 풀 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int arr[302][22], dp[22][302];
pii par[22][302];

int main() {
    int n, m; scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        int k; scanf("%d", &k);
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[k][j]);
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= j; k++) {
                if (dp[i][j] < dp[i - 1][j - k] + arr[k][i]) {
                    dp[i][j] = dp[i - 1][j - k] + arr[k][i];
                    par[i][j] = {i - 1, j - k};
                }
            }
        }
    }

    vector<int> ans;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        auto [ni, nj] = par[i][j];
        ans.push_back(j - nj);
        i = ni;
        j = nj;
    }
    printf("%d\n", dp[m][n]);
    for (int i = m - 1; i >= 0; i--) printf("%d ", ans[i]);
}