Algorithms

Backpack algo

  • 好早以前写的，搬运一下

01一维背包

  • 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int dp[100010]{};
    int n,m;
    cin>>m>>n;
    int v,w;
    while(n--){
        cin>>v>>w;
        for(int i = m ; i >= v; i--) dp[i]=max(dp[i],dp[i-v]+w);
    }
    cout<<dp[m];
}

01背包二维

  • 有 n(1 ≤ n ≤ 100) 种物品要放到一个袋子里，袋子的总容量为 m(1 ≤ m ≤ 100) ，我们一共有 k(1 ≤ k ≤ 100) 点体力值。第 i 种物品的体积为 vi(1 ≤ vi ≤ 100) ，把它放进袋子里会获得 wi(1 ≤ wi ≤ 100) 的收益，并且消耗我们 ti(1 ≤ ti ≤ 100) 点体力值，每种物品只能取一次，问如何选择物品，使得在物品的总体积不超过 m 并且花费总体力不超过 k 的情况下，获得最大的收益？请求出最大收益。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, m;
    cin>>k>>m>>n;
    int dp[440][440]{};
    int v, t, w;
    while(n--){
        cin>>v>>t>>w;
        for(int i = k; i >= v; i--){
            for(int j = m; j >= t; j--){
                dp[i][j] = max(dp[i][j],dp[i-v][j-t]+w);
            }
        }
    }
    cout<<dp[k][m];
    return 0;
}

完全背包

  • 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，每种物品能用无限多次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int dp[100010]{};
    int m, n;
    cin>>m>>n;
    int v,w;
    while(n--){
        cin>>v>>w;
        for(int i = v; i <= m; i++){
            dp[i]=max(dp[i],dp[i-v]+w);
        }
    }
    cout<<dp[m];
}

多重背包

  • 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    int dp[100010]{};
    cin>>n>>m;
    int w, v, l;
    for(int i = 0 ; i < n ; i ++){
        cin>>w>>v>>l;
        while(l--){
            for(int j = m; j >= v; j--){
                dp[j] = max(dp[j], dp[j-v] + w);
            }
        }
    }
    cout<<dp[m];
}

多重背包的单调队列优化

  • 多重背包的题: 有 n 种物品要放到一个袋子里，袋子的总容量为 m，第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000 多重背包的二进制优化 ： 题目同上，数据规模为 1 ≤ n, m, l ≤ 2000。用一个定理优化一下。定理：令 t 为最大的 i满足 2i+1 − 1 ≤ n，我们从 1, 2, 4, . . . , 2t, n − 2t+1 + 1 中选一些数字相加（可以不选），可以得出任意 [0, n] 内的值，每个数字只能用一次。每一种物品就只有 log l 个打包，然后对于每一组打包去跑 01 背包，可以把时间复杂度从 O(nm∑l) 降到 O(nm log∑l)。 但显然二进制优化不如单调队列优化，所以我们为什么不直接上单调队列优化呢？ 二进制优化的数据范围：题目同上，数据规模为 1 ≤ n, m, l ≤ 10000。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

//二进制优化，抄的谷粒多的板子
#include<bits/stdc++.h>
using namespace std;
int n, m, v, w, l;
int dp[2005];
int main() {
    cin >> n >> m;
    while (n--) {
        cin >> v >> w >> l;
        for (int k = 1; k <= l; l -= k, k <<= 1)
            for (int i = m; i >= v * k; i--)
                dp[i] = max(dp[i], dp[i - v * k] + w * k);
        for (int i = m; i >= v * l; i--)
            dp[i] = max(dp[i], dp[i - v * l] + w * l);
    }
    cout << dp[m];
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

//单调队列优化
//没看懂，还是抄的谷粒多板子。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
int n, m, V[210], W[210], C[210];
int f[20010], q[20010];
int calc(int i, int u, int k) {
    return f[u + k * V[i]] − k * W[i];
}
int main() {
    cin >> n >> m;
    memset(f, 0xcf, sizeof(f)); // −INF
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &V[i], &W[i], &C[i]);
        for (int u = 0; u < V[i]; u++) {
            int l = 1, r = 0;
            int maxp = (m - u) / V[i];
            for (int k = maxp - 1; k >= max(maxp - C[i], 0); k--) {
                while (l <= r && calc(i, u, q[r]) <= calc(i, u, k))
                    r--;
                q[++r] = k;
            }
            for (int p = maxp; p >= 0; p--) {
                while (l <= r && q[l] > p - 1) l++;
                if (l <= r)
                    f[u + p * V[i]] = max(f[u + p * V[i]], calc(i, u, q[l]) + p * W[i]);
                if (p - C[i] - 1 >= 0) {
                    while (l <= r && calc(i, u, q[r]) <= calc(i, u, p - C[i] - 1)) r--;
                    q[++r] = p - C[i] - 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans = max(ans, f[i]);
    cout << ans << endl;
}

分组背包

  • 有 n 种物品要放到一个袋子里，袋子的总容量为 m。第 i 个物品属于第 ai 组，每组物品我们只能从中选择一个。第 i 种物品的体积为 vi，把它放进袋子里会获得 wi 的收益，可以用 li 次，问如何选择物品，使得在物品的总体积不超过 m 的情况下，获得最大的收益？请求出最大收益。数据规模为 1 ≤ n, m, l ≤ 1000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, v, w, dp[1010]{}, a;
    cin>>n>>m;
    vector<pair<int,int>>c[1010];
    for(int i = 1; i<= n; i++)
    {
        cin>>a>>v>>w;
        c[a].push_back({v,w});
    }
    for(int i =0 ; i<=1000;i++){
        for(int j = m; j>=0; j--){
            for(auto [l,r]:c[i]){
                if(v<=j) dp[j]=max(dp[j],dp[j-l]+r);
            }
        }
    }
    cout<<dp[m];
    return 0;
}

混合背包

  • 混合背包比较愚蠢，很显然，如果是01，那么就直接取01；如果是完全，那就完全，如果是多重那就多重。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int dp[100010]{}, n, m;
    cin>>n>>m;
    int t, v, w;
    while(n--){
        cin>>t>>v>>w;
        if(t==1){
            for(int i = m; i >= v; i--) dp[i] = max(dp[i], dp[i-v] + w);
        }
        else if(t==0){
            for(int i = v; i <= m; i++) dp[i] = max(dp[i], dp[i-v] + w);
        }
        else {
            while(t--){
                for(int i = m; i>= v; i--) dp[i] = max(dp[i], dp[i-v] + w);
            }
        }
    }  
    cout<<dp[m];
    return 0;
}

有依赖的背包

  • 题目：金明有 n 元钱，想要买 m 个物品，第 i 件物品的价格为: ，重要度为: 。有些物品是从属于某个主件物品的附件，要买这个物品，必须购买它的主件。
  • 目标是让所有购买的物品的: 之和最大。
  • 这种题目比较愚蠢，就懒得写代码了，把主件当01背包做，把附件的代码+主件的代价，再把附件当做分组背包做即可。

k优解

  • 不会

前后缀分解

  • 显然对于01背包而言，存在需要放进去的物品和不需要放进去的物品，现在清楚姐姐有个问题，题目如下：

  • 清楚姐姐最近学会了01背包，01背包是背包问题中最简单的问题。

  • 01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。

  • 如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

  • 现在清楚姐姐有N个蝴蝶结，第i个蝴蝶结的体积为 ，好看程度为 ，她准备了一个容量大小为M的包包。她可以从这N个蝴蝶结中任选若干个放入背包，但是所选蝴蝶结的体积总和不能大于背包的容量M，清楚姐姐想要让所选蝴蝶结的好看程度总和最大化。

  • 她运用自己刚刚学会的01背包知识，快速算出了她能用她的包包装下蝴蝶结好看程度总和的最大值。现在清楚姐姐有了一个新的问题，我们定义原问题的答案，即所选蝴蝶结好看程度总和的最大值为 。

  • 定义从这NN个蝴蝶结中去掉第i个蝴蝶结后，从剩余N−1个蝴蝶结中任选若干个放入背包，所选蝴蝶结好看程度总和的最大值为 。若 < ，则称第ii个蝴蝶结为一个“必选蝴蝶结”。

  • 清楚姐姐现在获得了调整蝴蝶结好看程度的机会，她想要知道，对于第i个蝴蝶结，在它初始好看程度的基础上，再加上多少，该蝴蝶结就能够成为一个“必选蝴蝶结”。

  • 数据范围: n,m<5000, <m <1e9

  • 题解 设f[i][j]是前i个物品中重量总和为j时的最大值，g[i][j]是后i个物品中重量总和为j时的最大值，显然这两个都可以O(nm)求，对于每个物品i，只需要遍历f[i-1][j]中的j，然后最大值就是f[i-1][j]+g[i+1][m-j]，这样对于每个物品可以用O(m)求出答案，总体是O(nm)的，求出最大值之后，再从0遍历到m-w[i]，再次求一遍前后最大值，这样求出的最大值就是不包含自己且背包大小为m-w[i]时的最大价值，然后再用原本的数值+1-这个值-v[i]就是这个的答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

//sample
/*4 100
100 100
99 10
1 2
5 5*/
//answer
/*0
89
89
94*/
//sample
/*3 1
1 100
1 100
1 100*/
//answer
/*1
1
1*/
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    ll f[n + 1][m + 1], g[n + 1][m + 1];
    for (int i = 0; i <= n ; i++)
        for (int j = 0; j <= m ; j++)
            f[i][j] = 0, g[i][j] = 0;
    int v[n + 1], w[n + 1];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j <= m; j++) {
            f[i+1][j] = f[i][j];
        }
        for (int j = m; j >= w[i]; j--) {
            f[i + 1][j] = max(f[i + 1][j], f[i][j - w[i]] + v[i]);
        }
    }
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j <= m; j++) {
            g[i-1][j] = g[i][j];
        }
        for (int j = m; j >= w[i]; j--) {
            g[i - 1][j] = max(g[i - 1][j], g[i][j - w[i]] + v[i]);
        }
    }
    ll l = 0, r = 0 ;
    for (int i = 0; i < n; i++) {
        l = 0, r = 0;
        for (int j = 0; j <= m; j++) {
            r = max(r, f[i][j] + g[i][m - j]);
            if (j + w[i] <= m) l = max(l, f[i][j] + g[i][m - w[i] - j] + v[i]);
        }
        ll ans = r - l + 1;
        cout<<max(0ll,ans)<<endl;
    }
    return 0;
}

01背包+线段树

  • 你真该死啊
© 2022 - 2025 ColommarWei
If you have any questions, please contact me via the repo. Issues are welcome.
Built with Hugo
Theme Stack designed by Jimmy