여행 계획

여행 경로 최적화 코드를 살펴보겠습니다.

#include <iostream>
using namespace std;
long long capacity[1000200], demand[1000200], sum[1000200], queue[1000200], visited[1000200];
int main() {
    int n;
    cin >> n;
    for (long long i = 1; i <= n; i++) cin >> capacity[i] >> demand[i];

    for (long long i = 1; i <= n; i++) sum[i + n] = sum[i] = capacity[i] - demand[i];
    for (long long i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1];
    long long head = 0, tail = 0;
    queue[0] = 2 * n + 1, tail = 1;
    for (long long i = 2 * n; i >= 0; i--) {
        while (head < tail && queue[head] > i + n) head++;
        if (i < n)
            if (sum[queue[head]] - sum[i] >= 0)
                visited[i + 1] = 1;
        while (head < tail && sum[queue[tail - 1]] >= sum[i]) tail--;
        queue[tail++] = i;
    }

    demand[0] = demand[n];
    for (long long i = 1; i <= n; i++) sum[i + n] = sum[i] = capacity[i] - demand[i - 1];
    for (long long i = 1; i <= 2 * n; i++) sum[i] += sum[i - 1];
    head = 0, tail = 0;
    queue[0] = 0, tail = 1;
    for (long long i = 1; i <= 2 * n; i++) {
        while (head < tail && queue[head] < i - n) head++;
        if (i > n)
            if (sum[i] - sum[queue[head]] >= 0)
                visited[i - n] = 1;
        while (head < tail && sum[queue[tail - 1]] <= sum[i]) tail--;
        queue[tail++] = i;
    }

    for (long long i = 1; i <= n; i++) {
        if (visited[i]) cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}

동전 문제

이 문제는 각 항목에 제한된 수량이 있는 다중 배낭 문제입니다. 기본적인 다중 배낭 문제 템플릿을 사용할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int value[105], count[105], dp[105][105]; // dp[i][j]: 처음 i개의 동전만 사용하여 j만큼의 금액을 만드는 데 필요한 동전의 최소 개수
int main() {
    int m, n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> value[i];
    for (int i = 1; i <= n; i++) cin >> count[i];
    cin >> m;
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= count[i]; k++)
                if (j - k * value[i] >= 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - k * value[i]] + k);
    cout << dp[n][m];
    return 0;
}

시간 복잡도를 줄이기 위해 이진 분해를 활용한 방법도 있습니다.

#include <bits/stdc++.h>
using namespace std;
int weight[59], value[59], count[59], dp[59][59];
int main() {
    int n, w, v, c, s = 0, V;
    cin >> V >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w >> v >> c;
        for (int j = 1; j <= c; j <<= 1) {
            weight[++s] = j * w;
            value[s] = j * v;
            c -= j;
        }
        if (c > 0) {
            weight[++s] = c * w;
            value[s] = c * v;
        }
    }
    for (int i = 1; i <= s; i++)
        for (int j = 1; j <= V; j++)
            if (j >= weight[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            else
                dp[i][j] = dp[i - 1][j];
    cout << dp[s][V];
    return 0;
}

또한 동전 문제를 풀 때 이진 분해와 함께 실행하는 방법도 있습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int value[210], count[210], dp[20010];
void dynamicProgramming(int w, int c) {
    for (int i = dp[0]; i >= w; i--)
        dp[i] = min(dp[i], dp[i - w] + c);
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &value[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &count[i]);
    int m;
    scanf("%d", &m);
    memset(dp, 0x3f, sizeof(dp)), dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= count[i]; j <<= 1)
            dynamicProgramming(value[i] * j, j), count[i] -= j;
        if (count[i]) dynamicProgramming(value[i] * count[i], count[i]);
    }
    printf("%d\n", dp[m]);
    return 0;
}