忙里偷闲温习背包九讲，刷了几道背包题

小码匠

发布于 2024-02-21 13:15:14

660

发布于 2024-02-21 13:15:14

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好！我是小码匠。

先分享这两天游玩的照片。

偶遇猫咪

忙里偷闲，老码农又让我温习了背包九讲。

今天分享几道背包问题的代码。

[ABC321F] #(subset sum = K) with Add and Erase

https://www.luogu.com.cn/problem/AT_abc321_f

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5005;
const int mod = 998244353;
int dp[maxn];

void best_coder() {
    int q, k;
    cin >> q >> k;
    dp[0] = 1;
    while (q--) {
        char a;
        int b;
        cin >> a >> b;
        if (a == '+') {
            for (int i = k; i >= b; --i) {
                dp[i] += dp[i - b];
                dp[i] %= mod;
            }
        } else {
            for (int i = b; i <= k; ++i) {
                dp[i] = (dp[i] - dp[i - b] + mod) % mod;
//                dp[i] %= mod;
            }
        }

        cout << dp[k] << '\n';
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

AT_dp_e Knapsack 2

https://www.luogu.com.cn/problem/AT_dp_e

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;
int dp[maxn];

struct thing {
    int w;
    int v;
} a[105];

void best_coder() {
    int n, W;
    cin >> n >> W;
    int m = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].w >> a[i].v;
        m += a[i].v;
    }
    for (int i = 1; i <= m; ++i) {
        dp[i] = INT_MAX;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = m; j >= a[i].v; --j) {
            if (dp[j - a[i].v] != INT_MAX) {
                if (dp[j - a[i].v] + a[i].w <= W) {
                    dp[j] = min(dp[j], dp[j - a[i].v] + a[i].w);
                }
            }
        }
    }

    for (int i = m; i >= 0; --i) {
        if (dp[i] != INT_MAX) {
            cout << i;
            return;
        }
    }

}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

CF687C The Values You Can Make

https://www.luogu.com.cn/problem/CF687C
代码 #include <bits/stdc++.h> using namespace std; int dp[2005][2005]; //bool ans[505]; void best_coder() { int n, k; cin >> n >> k; memset(dp, 0, sizeof(dp)); dp[0][0] = true; // int ans = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; for (int j = k; j >= 0; --j) { for (int s = k; s >= 0; --s) { dp[j + x][s] |= dp[j][s]; dp[j][s + x] |= dp[j][s]; } } } int cnt = 0; for (int i = 0; i <= k; ++i) { if (dp[i][k - i]) { ++cnt; } } cout << cnt << '\n'; for (int i = 0; i <= k; ++i) { if (dp[i][k - i]) { cout << i << " "; } } } void happy_coder() { } int main() { // 提升cin、cout效率 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 小码匠 best_coder(); // 最优解 // happy_coder(); return 0; }

P4817 [USACO15DEC] Fruit Feast G

https://www.luogu.com.cn/problem/P4817

代码

#include <bits/stdc++.h>

using namespace std;

bool dp[10000005];
void best_coder() {
    int n, a, b;
    cin >> n >> a >> b;
    dp[0] = true;
    int ans = 0;
    for (int i = a; i <= n; ++i) {
        dp[i] |= dp[i - a];
    }
    for (int i = b; i <= n; ++i) {
        dp[i] |= dp[i - b];
    }
    for (int i = 1; i <= n; ++i) {
        if (dp[i]) {
            ans = max(ans, i);
            dp[i / 2] = true;
        }
    }
    for (int i = a; i <= n; ++i) {
        dp[i] |= dp[i - a];
        if (dp[i]) {
            ans = max(ans, i);
        }
    }
    for (int i = b; i <= n; ++i) {
        dp[i] |= dp[i - b];
        if (dp[i]) {
            ans = max(ans, i);
        }
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-02-04，如有侵权请联系 cloudcommunity@tencent.com 删除

cin