1231번: Stock Market

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

$O(ndL)$

주식을 전날 사서 오늘 파는 행위만으로도 최대 이윤을 만들 수 있다.
전날 주식값들을 무게, 오늘 주식값들을 가치라 생각하면
unbounded knapsack problem과 동치이다.

#include<cstdio>
#define max(x,y) x>y?x:y
int n, d, m, a[50][10], dp[500001];
int main() {
    scanf("%d%d%d", &n, &d, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < d; j++) scanf("%d", a[i] + j);
    for (int i = 1; i < d; i++) {
        for (int j = 0; j <= m; j++) dp[j] = j;
        for (int j = 0; j < n; j++)
            for (int k = a[j][i - 1]; k <= m; k++) dp[k] = max(dp[k], dp[k - a[j][i - 1]] + a[j][i]);
        m = dp[m];
    }
    printf("%d", m);
    return 0;
}