2662번: 기업투자

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

$O(nw^2)$

dp[i][j]: 1~j번 기업에 i원을 투자했을 때 얻을 수 있는 최대 이익

#include<cstdio>
int w, n, dp[301][21], fr[301][21], a[301][21];
void f(int x, int y) {
    if (!y) return;
    f(fr[x][y], y - 1);
    printf("%d ", x - fr[x][y]);
}
int main() {
    scanf("%d%d", &w, &n);
    for (int i = 1; i <= w; i++) {
        scanf("%*d");
        for (int j = 1; j <= n; j++) scanf("%d", a[i] + j);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = w; j; j--) {
            for (int k = 0; k <= j; k++) if (dp[j][i] < dp[j - k][i - 1] + a[k][i]) {
                dp[j][i] = dp[j - k][i - 1] + a[k][i];
                fr[j][i] = j - k;
            }
        }
    }
    printf("%d\n", dp[w][n]);
    f(w, n);
    return 0;
}

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;
}

9084번: 동전

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


$O(tnl)$

knapsack problem과 비슷하게 푼다.

#include<cstdio>
int t, n, m;
int main() {
    scanf("%d", &t);
    while (t--) {
        int dp[10001] = { 1 };
        scanf("%d", &n);
        for (int i = 0, x; i < n; i++) {
            scanf("%d", &x);
            for (int j = x; j <= 10000; j++) dp[j] += dp[j - x];
        }
        scanf("%d", &m);
        printf("%d\n", dp[m]);
    }
    return 0;
}

1093번: 스티커 수집

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


$O(n2^{n/2})$

knapsack problem을 O(n2^(n/2))에 푸는 방법이 있다.
(https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle)
이를 이용해 가치를 k 이상 얻기 위해 써야하는 최소 비용 r을 구할 수 있다.
처음 가지고 있는 스티커를 돈으로 환산하여 합한 값이 s라 하면
답은 max(r-s,0)이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, v[32], c[32], k, s, cnt[2] = { 1,1 }, r = 1e9;
pair<int, int> p[2][1 << 16];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", c + i);
    for (int i = 0; i < n; i++) scanf("%d", v + i);
    scanf("%d%d", &k, &m);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &x);
        s += c[x];
    }
    for (int i = 0; i < n; i++) {
        int h = i >= n / 2;
        for (int j = 0; j < cnt[h]; j++) p[h][j + cnt[h]] = { p[h][j].first + v[i],p[h][j].second + c[i] };
        cnt[h] *= 2;
    }
    sort(p[1], p[1] + cnt[1]);
    for (int j = cnt[1] - 1; j--;) p[1][j].second = min(p[1][j].second, p[1][j + 1].second);
    for (int i = 0; i < cnt[0]; i++) {
        int lb = lower_bound(p[1], p[1] + cnt[1], make_pair(k - p[0][i].first, 0)) - p[1];
        if (lb < cnt[1]) r = min(r, p[0][i].second + p[1][lb].second);
    }
    printf("%d", r < 1e9 ? max(r - s, 0) : -1);
    return 0;
}

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;
}

13137번: Exchange Problem

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


$O(np)$

unbounded knapsack problem 솔루션을 변형한다.

#include<cstdio>
int n, dp[100001];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        for (int j = x; j <= 1e5; j++) if (dp[j] && dp[j] <= dp[j - x]) {
            puts("No");
            return 0;
        }
        else dp[j] = dp[j - x] + 1;
    }
    puts("Yes");
    return 0;
}

11052번: 붕어빵 판매하기

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


$O(n^2)$

knapsack problem 이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, dp[1001];
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for (int j = i; j <= n; j++) dp[j] = max(dp[j], dp[j - i] + x);
    }
    printf("%d", dp[n]);
    return 0;
}

1423번: 원숭이 키우기 - bounded knapscak problem으로 풀어보기

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


저지 사이트에 언급 되지 않은 몇 가지 유의사항이 있다.
- 캐릭터 수는 d를 넘을 수 있다.
- 캐릭터 수가 매우 많을 수 있으므로 답은 int 범위가 넘어갈 수 있다.


$O(n^2d^2)$

일단 초기 힘의 합을 구해 놓는다. 그리고 훈련 기간보다 많은 사람을 훈련시킬 수 없으므로 캐릭터 수가 d보다 크다면 d라고 가정한다.
이제
dp[훈련기간]: 해당 훈련 기간이내 추가할 수 있는 최대 힘의 합
이라고 정의한 점화식을 knapsack problem 해결법 비슷하게 풀 수 있다.
해당 기간에서 각 캐릭터가 얼만큼 레벨을 올리는 지에 따라 dp 배열을 갱신해나가면 문제를 해결할 수 있다. 캐릭터의 총 수는 최대 nd이므로 시간 안에 해결할 수 있을 것이다.
구현은 해보지 않았지만 bounded knapsack problem 해결법을 이용한다면 $n^2d$시간에도 가능할 듯하다.

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long lint;
int n, d, p[51], q[51];
lint r, dp[101];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", p + i);
    for (int i = 1; i <= n; i++) scanf("%d", q + i);
    scanf("%d", &d);
    for (int i = 1; i <= n; i++) r += (lint)p[i] * q[i], p[i] = min(d, p[i]);
    for (int i = 1; i <= n; i++)
        while (p[i]--) for (int j = d; j >= 0; j--)
            for (int k = i + 1; k <= n&&k + j - i <= d; k++)
                dp[k + j - i] = max(dp[k + j - i], dp[j] + q[k] - q[i]);
    printf("%lld", dp[d] + r);
    return 0;
}

2293번: 동전 1

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

$O(nk)$

Unbounded Knapsack Problem 이다.

#include<stdio.h>
int dp[10001], n, k;
int main() {
    dp[0] = 1;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        for (int j = a; j <= k; j++) dp[j] += dp[j - a];
    }
    printf("%d", dp[k]);
    return 0;
}