背包DP

01 背包：对于每一种物品只有选 (1 次)或不选

for (int i = 1;i <= n;i++) {
	for (int j = m;j >= v[i];j--) {
		f[j] = max(f[j], f[j - v[i]] + a[i]);
	}
}

完全背包：每种物品可以选择任意次 $[0, \infty)$

for (int i = 1;i <= n;i++) {
	for (int j = v[i];j <= m;j++) {
		f[j] = max(f[j], f[j - v[i]] + a[i]);
	}
}

多重背包：每种物品可以选择 $[0, s_{i}]$ 件

P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态
朴素算法： $O (N M \sum k_{i})$

for (int i = 1;i <= n;i++) {
	for (int j = m;j >= v[i];j--) {
		for (int k = 0;k <= s[i] and k * v[i] <= j;k++) {
			f[j] = max(f[j], f[j - k * v[i]] + k * a[i]);
		}
	}
}

二进制优化： $O (N M \sum \log k_{i})$
转化为 01 背包解决问题

int f[M], v[N * (lenK)_2], w[N * (lenK)_2];
void solve() {
    int n, m;cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int b, a, k;cin >> b >> a >> k;
        for (int j = 1;j <= k;j <<= 1) {
            v[++cnt] = j * a;w[cnt] = j * b;k -= j;
        }
        if (k)v[++cnt] = k * a, w[cnt] = k * b;
    }
    for (int i = 1;i <= cnt;i++) {
        for (int j = m;j >= v[i];j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << '\n';
}

单调队列优化： $O (N M)$
(没看懂)

int f[40010], g[40010];
int main() {
    int n, W;cin >> n >> W;       //宝物种数,最大载重
    for (int i = 1;i <= n;i++) {  //枚举宝物
        memcpy(g, f, sizeof(f));  //f备份到g       
        int v, w, m;cin >> v >> w >> m;        //价值 重量 数量
        for (int j = 0;j < w;j++) {  //分拆成w个类 
            deque<int> q;            //单调队列
            for (int k = j;k <= W;k += w) { //滑动窗口[k-m*w,k-w]
                while (!q.empty() && q.front() < k - m * w) q.pop_front();
                while (!q.empty() && g[k] >= g[q.back()] + (k - q.back()) / w * v) q.pop_back();
                q.push_back(k);
                if (!q.empty()) f[k] = max(g[k], g[q.front()] + (k - q.front()) / w * v);
            }
        }
    }
    cout << f[W] << '\n';
}

混合背包：01 背包+完全背包+分组背包

遇到混合背包问题，可以将多重背包和 01 背包用二进制优化一起处理，而完全背包单独处理。

分组背包：所有物品分为若干组，对于每组背包中的物品，最多只能选择一个

分组背包不能使用二进制/单调队列优化

for (int i = 1;i <= n;i++) {  
    for (int j = m;j >= 1;j--) 
        for (int k = 0;k <= s[i];k++) 
            if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);//v[i][k]代表第i组第k个
}

或在线读入

for (int i = 1;i <= n;i++) { 
    // 对于每一组的物品
    cin >> s;
    for (int j = 1;j <= s;j++) cin >> v[j] >> w[j];
    for (int j = m;j >= 1;j--) 
        for (int k = 0;k <= s;k++) 
            if (j >= v[k]) f[j] = max(f[j], f[j - v[k]] + w[k]);
}

求背包方案数：

01 背包：

int f[N], c[N];
// f[i]表示背包容量为i时最优选法的总价值
// c[i]表示背包容量为i时最优选法的方案数

void solve() {
    int n, m, v, w;
    cin >> n >> m;
    for (int i = 0;i <= m;i++) c[i] = 1;

    for (int i = 1; i <= n; i++) {    //枚举物品
        cin >> v >> w;
        for (int j = m; j >= v; j--) {  //枚举体积
            if (f[j - v] + w > f[j]) {      //装新物品总价值更大
                f[j] = f[j - v] + w;
                c[j] = c[j - v];
            } else if (f[j - v] + w == f[j]) //装新物品总价值相等
                c[j] = (c[j] + c[j - v]) % mod;
        }
    }
    cout << c[m] << '\n';
}

恰好装满的 01 背包

int f[N], c[N];
// f[i]表示背包容量为i时最优选法的总价值
// c[i]表示背包容量为i时最优选法的方案数

void solve() {
    int n, m, v, w;
    cin >> n >> m;
    for (int i = 0;i <= m;i++) f[i] = -1000;
    f[0] = 0;c[0] = 1;

    for (int i = 1; i <= n; i++) {    //枚举物品
        cin >> v >> w;
        for (int j = m; j >= v; j--) {  //枚举体积
            if (f[j - v] + w > f[j]) {      //装新物品总价值更大
                f[j] = f[j - v] + w;
                c[j] = c[j - v];
            } else if (f[j - v] + w == f[j]) //装新物品总价值相等
                c[j] = (c[j] + c[j - v]) % mod;
        }
    }
    cout << c[m] << '\n';
}

P 1048 采药

背包板子

int f[110][1100];
void solve() {
    int t, n;cin >> t >> n;
    vector<int> v(n + 1), a(n + 1);
    for (int i = 1;i <= n;i++)cin >> v[i] >> a[i];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= t;j++) {
            if (j < v[i])f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + a[i]);
        }
    }
    cout << f[n][t] << '\n';
}

优化

int f[1100];
void solve() {
    int t, n;cin >> t >> n;
    vector<int> v(n + 1), a(n + 1);
    for (int i = 1;i <= n;i++)cin >> v[i] >> a[i];
    for (int i = 1;i <= n;i++) {
        for (int j = t;j >= v[i];j--) {
            f[j] = max(f[j], f[j - v[i]] + a[i]);
        }
    }
    cout << f[t] << '\n';
}

P1060 开心的金明

背包板子

int f[30010];
void solve() {
    int t, n;cin >> t >> n;
    vector<int> v(n + 1), a(n + 1);
    for (int i = 1;i <= n;i++)cin >> v[i] >> a[i];
    for (int i = 1;i <= n;i++) {
        for (int j = t;j >= v[i];j--) {
            f[j] = max(f[j], f[j - v[i]] + a[i] * v[i]);
        }
    }
    cout << f[t] << '\n';
}

P1855 榨取kkksc03

二维费用背包

int f[210][210];
void solve() {
    int n, m, t;cin >> n >> m >> t;
    vector<int>a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i] >> b[i];
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= a[i];j--) {
            for (int k = t;k >= b[i];k--) {
                f[j][k] = max(f[j][k], f[j - a[i]][k - b[i]] + 1);
            }
        }
    }
    cout << f[m][t] << '\n';
}

P5020 货币系统

看某个数是否可以由数组中的其他元素 (每个元素无限使用)组成。

void solve() {
    int n;cin >> n;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    int ans = n;
    vector<int> f(3e4);f[0] = 1;
    for (int i = 1;i <= n;i++) {
        if (f[a[i]]) {
            ans--;continue;
        }
        for (int j = a[i];j <= a[n];j++) {
            f[j] = f[j] | f[j - a[i]];
        }
    }
    cout << ans << '\n';
}

或者也可以一个一个加去标记。

P1757 通天之分组背包

分组背包模板类型

void solve() {
    int m, n;cin >> m >> n;
    vector<int> w(n + 1), v(n + 1), b(n + 1);int t = 0;
    vector<vector<int>> g(101, vector<int>(101));
    for (int i = 1;i <= n;i++) {
        int x;cin >> w[i] >> v[i] >> x;
        t = max(t, x);b[x]++;
        g[x][b[x]] = i;
    }
    vector<int> f(m + 1);
    for (int i = 1;i <= t;i++) {
        for (int j = m;j >= 0;j--) {
            for (int k = 1;k <= b[i];k++) {
                if (j >= w[g[i][k]]) {
                    f[j] = max(f[j], f[j - w[g[i][k]]] + v[g[i][k]]);
                }
            }
        }
    }
    cout << f[m] << '\n';
}

P1064 金明的预算方案

01 背包：

选择 f[j]=f[j - v[i]] + a[i]
不选 f[j] 不变，去选择下一个。

此题目：

不选，看下一个
选择一个主件
选择主件且选择附件 1
选择主件且选择附件 2
选择主件且选择附件 1，附件 2

将主件和附件预处理一下，按照 01 背包来做即可。

int f[40010];
void solve() {
    int m, n;cin >> m >> n;
    vector<array<int, 3>> v(n + 1), p(n + 1);
    for (int i = 1;i <= n;i++) {
        int _v, _p, _q;cin >> _v >> _p >> _q;
        if (!_q)v[i][0] = _v, p[i][0] = _p;
        else {
            if (!v[_q][1]) v[_q][1] = _v, p[_q][1] = _p;
            else v[_q][2] = _v, p[_q][2] = _p;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 0;j--) {
            if (j >= v[i][0]) {//买主件
                f[j] = max(f[j], f[j - v[i][0]] + p[i][0] * v[i][0]);
            }
            if (j >= v[i][0] + v[i][1]) {//买第1个附件
                f[j] = max(f[j], f[j - (v[i][0] + v[i][1])] + p[i][0] * v[i][0] + p[i][1] * v[i][1]);
            }
            if (j >= v[i][0] + v[i][2]) {//买第2个附件
                f[j] = max(f[j], f[j - (v[i][0] + v[i][2])] + p[i][0] * v[i][0] + p[i][2] * v[i][2]);
            }
            if (j >= v[i][0] + v[i][1] + v[i][2]) {//买第1,2个附件
                f[j] = max(f[j], f[j - (v[i][0] + v[i][1] + v[i][2])] 
                + p[i][0] * v[i][0] + p[i][1] * v[i][1] + p[i][2] * v[i][2]);
            }
        }
    }
    cout << f[m] << '\n';
}

P 2946 Cow Frisbee Team S

01 背包变形

$d p [i] [j]$ 代表在前 $i$ 个牛中之和 $\mod f = j$ 的方案数

对于数组中某个元素只有选和不选

若不选择 $i$ ：则只需要前 $i - 1$ 头牛凑出 $\mod f = j$ 即： $d p [i - 1] [j]$

若选择 $i$ ：则需要前 $i - 1$ 头牛凑出 $\mod f = j - a [i]$ .即： $d p [i - 1] [j - a [i]]$

$d p [i] [j] = d p [i] [j] + d p [i - 1] [j] + d p [i - 1] [j - a [i]]$

还可以用滚动数组优化。

#define int long long
constexpr int mod = 1e8;
int dp[2010][2010];
void solve() {
    int n, f;cin >> n >> f;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;x %= f;a[i] = x;dp[i][x] = 1;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= f - 1;j++) {
            dp[i][j] = ((dp[i][j] + dp[i - 1][j]) % mod + dp[i - 1][(j - a[i] + f) % f] % mod) % mod;
        }
    }
    cout << dp[n][0] << '\n';
}

P1776 宝物筛选

Solution

多重背包/二进制优化/单调队列优化

若按照普通多重背包会卡得很极限 (927 ms)，于是需要优化。

int f[40010];
void solve() {
    int n, m;cin >> n >> m;vector<array<int, 3>>a(n + 1);
    for (int i = 1;i <= n;i++) {
        int v, w, k;cin >> v >> w >> k;a[i] = {v,w,k};
    }
    for (int i = 1;i <= n;i++) {
        for (int j = m;j >= 0;j--) {
            for (int k = 0;k <= a[i][2] and j >= k * a[i][1];k++) {
                f[j] = max(f[j], f[j - k * a[i][1]] + k * a[i][0]);
            }
        }
    }
    cout << f[m] << '\n';
}

二进制优化：(20 ms)
v,w 数组长度最多达到 $n \times b i t = 100 \times (\leq (10^{5})_{10} < (20)_{2_{l e n}}) < 2000$

int f[40010], v[2000], w[2000];
void solve() {
    int n, m;cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int b, a, k;cin >> b >> a >> k;
        for (int j = 1;j <= k;j <<= 1) {
            v[++cnt] = j * a;w[cnt] = j * b;k -= j;
        }
        if (k)v[++cnt] = k * a, w[cnt] = k * b;
    }
    for (int i = 1;i <= cnt;i++) {
        for (int j = m;j >= v[i];j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << '\n';
}

单调队列优化：

int f[40010], g[40010];
int main() {
    int n, W;cin >> n >> W;       //宝物种数,最大载重
    for (int i = 1;i <= n;i++) {  //枚举宝物
        memcpy(g, f, sizeof(f));  //f备份到g       
        int v, w, m;cin >> v >> w >> m;        //价值 重量 数量
        for (int j = 0;j < w;j++) {  //分拆成w个类 
            deque<int> q;            //单调队列
            for (int k = j;k <= W;k += w) { //滑动窗口[k-m*w,k-w]
                while (!q.empty() && q.front() < k - m * w) q.pop_front();
                while (!q.empty() && g[k] >= g[q.back()] + (k - q.back()) / w * v) q.pop_back();
                q.push_back(k);
                if (!q.empty()) f[k] = max(g[k], g[q.front()] + (k - q.front()) / w * v);
            }
        }
    }
    cout << f[W] << '\n';
}

P1833 樱花

混合背包

遇到混合背包问题，可以将多重背包和 01 背包用二进制优化一起处理，而完全背包单独处理。

int f[1010], v[100010], w[100010], a[100010];
void solve() {
    int aa, b, c, d;char cc1, cc2;cin >> aa >> cc1 >> b >> c >> cc2 >> d;
    int m = 60 * c + d - 60 * aa - b;
    int n;cin >> n;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int t, c, p;cin >> t >> c >> p;
        if (!p) {//无限制->完全背包
            v[++cnt] = t;w[cnt] = c;
        }
        for (int j = 1;j <= p;j <<= 1) {//多重背包和01背包->01背包
            v[++cnt] = j * t;w[cnt] = j * c;a[cnt] = 1; p -= j;
        }
        if (p)v[++cnt] = p * t, w[cnt] = p * c, a[cnt] = 1;
    }
    for (int i = 1;i <= cnt;i++) {
        if (a[i]) {//01背包
            for (int j = m;j >= v[i];j--) {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        } else {//完全背包
            for (int j = v[i];j <= m;j++) {
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        }
    }
    cout << f[m] << '\n';
}

P1156 垃圾陷阱

本题易得掉下来一个垃圾就可以马上处理一个垃圾，因此按照垃圾掉落顺序来处理。

对于垃圾而言只有两种处理方式，要么吃掉垃圾维持生命，要么堆高度。

$f [i] [j]$ 表示在处理了前 $i$ 个垃圾在高度 $j$ 时的最大血量

若用来维持生命了，那么这时的高度和之前相比并不会变化，但是这时的生命加上了 l
若来堆高度，那么这时的高度就增加了 h

转移方程： $f [i] [j] = max (f [i - 1] [j] + l, f [i - 1] [j - h])$

int f[110][110];
void solve() {
    int d, n;cin >> d >> n;vector<array<int, 3>>a(n + 1);   
    for (int i = 1;i <= n;i++) {
        int t, l, h;cin >> t >> l >> h;a[i] = {t,l,h};
    }
    sort(a.begin() + 1, a.end(), [&](auto x, auto y) {
        return x[0] < y[0];
        });
    f[0][0] = 10;
    for (int i = 1;i <= n;i++) {
        for (int j = 0; j <= d;j++) {
            auto [t, l, h] = a[i];
            if (f[i - 1][j] >= t) {
                f[i][j] = max(f[i][j], f[i - 1][j] + l);
            }
            if (j >= h && f[i - 1][j - h] >= t) {
                f[i][j] = max(f[i][j], f[i - 1][j - h]);
            }
        }
    }
    int mh = 0, mt = 0, i;
    for (i = 1;i <= n;i++) {
        for (int j = 0;j <= d;j++) {
            auto [t, l, h] = a[i];
            if (f[i][j] >= t)mh = max(mh, j);
            mt = max(mt, f[i][j]);
        }
        if (mh == d)break;
    }
    if (mh == d)cout << a[i][0] << '\n';
    else cout << mt << '\n';
}

int f[110];
void solve() {
    int d, n;cin >> d >> n;vector<array<int, 3>>a(n + 1);
    for (int i = 1;i <= n;i++) {
        int t, l, h;cin >> t >> l >> h;a[i] = {t,l,h};
    }
    sort(a.begin() + 1, a.end(), [&](auto x, auto y) {
        return x[0] < y[0];
        });
    f[0] = 10;
    for (int i = 1;i <= n;i++) {
        for (int j = d;j >= 0;j--) {
            auto [t, l, h] = a[i];
            if (f[j] >= t) {
                if (j + h >= d) {
                    cout << t << '\n';return;
                }
                f[j + h] = max(f[j + h], f[j]);
                f[j] += l;
            }
        }
    }
    cout << f[0] << '\n';
}

P 5322 排兵布阵

Solution

分组背包

我自己的的分组背包时间复杂度过高了 $(O (n m s + m s^{2}))$ 会 T 掉两个点

本处的背包：总委派人数即总容量 ( $\sum v_{i} \leq s$ )
分组：每个城堡即为一组，每组委派人数不超过 $v_{i}$ 人，若委派 $k$ 人则在这个城堡的收益为 $w_{i, k}$ ，共 $m$ 组, 每组中的物品就是可能选择的人数，每组只能选择一个。

$v_{i}$ 代表对于第 $i$ 个城堡最大委派人数 ( $2 max (x_{i}) + 1 (x_{i} 代表某城堡各玩家委派的人数)$ )
$w_{i, k}$ 代表第 $i$ 个城堡委派 $k$ 个人可以在第 $i$ 个城堡中得到的总收益

此处 T 掉的原因是我 $s$ 循环了两次，本题 $s$ 范围较大 ( $2 \times 10^{4}$ )，而 $n, m$ 范围较小 ( $100$ )，应尽量多利用数据范围较小的数据，所以需要另找方法，当 $s$ 范围小时也不失为一种办法。

本处是多进行了计算，这里是将 $[0, v_{i}]$ 范围内的所有可能都遍历了一遍，而根本不需要那么多，这里的复杂度应是 $O (n)$ 级别，因为最优的情况只需要考虑 $[a_{1} \times 2 + 1, a_{2} \times 2 + 1, \dots, a_{n} \times 2 + 1]$ ,共 $n$ 种情况。

int f[20010], v[110], w[110][20010], a[110][110];
void solve() {
    int n, m, s;cin >> n >> m >> s;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1;i <= m;i++) {
        int mx = -1;
        for (int j = 1;j <= n;j++) {
            mx = max(mx, a[j][i]);
        }
        v[i] = mx * 2 + 1;
    }
    for (int i = 1;i <= m;i++) {
        for (int k = 0;k <= v[i];k++) {
            for (int j = 1;j <= n;j++) {
                if (a[j][i] * 2 < k) {
                    w[i][k] += i;
                }
            }
        }
    }
    for (int i = 1;i <= m;i++) {
        for (int j = s;j >= 0;j--) {
            for (int k = 0;k <= min(v[i], j);k++) {
                f[j] = max(f[j], f[j - k] + w[i][k]);
            }
        }
    }
    cout << f[s] << '\n';
}

突破点：排序：本处若进行排序的话，大于某值，也同样大于前面的值，即取到第 $k$ 个城堡，这时获得的分数就为 $k \times i$ ,这时需要委派的人数就一定是 $2 x_{k} + 1$
注意：处理排序需要读入时反着读入。

时间复杂度 $O (n m s)$ ，这样就将最后一维 $O (s) \to O (n)$

int f[20010], a[110][110];
void solve() {
    int n, m, s;cin >> n >> m >> s;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[j][i];
        }
    }
    for (int i = 1;i <= m;i++) {
        sort(a[i] + 1, a[i] + 1 + n);
        for (int j = 1;j <= n;j++) {
            a[i][j] = a[i][j] * 2 + 1;
        }
    }
    for (int i = 1;i <= m;i++) {
        for (int j = s;j >= 0;j--) {
            for (int k = 1;k <= n;k++) {
                if (j >= a[i][k])f[j] = max(f[j], f[j - a[i][k]] + k * i);
            }
        }
    }
    cout << f[s] << '\n';
}