1535번: 안녕

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


$O(na)$

0/1 knapsack 문제이다.

#include<cstdio>
int n, dp[100], a[20];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        for (int j = 99; j >= a[i]; j--) if (dp[j] < dp[j - a[i]] + x) dp[j] = dp[j - a[i]] + x;
    }
    printf("%d", dp[99]);
    return 0;
}