【算法】背包问题应用

01 背包

AcWing 423. 采药

代价： 采药时间 T
价值： w
0 - 1背包问题

#include 
using namespace std;

const int N = 1010;

int n, m;

int f[N];

int main() {
    
    cin >> m >> n;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[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

AcWing 1024. 装箱问题

总代价： 箱子容量 V
代价： 小物品体积
价值： 小物品体积
0-1背包问题

#include 
using namespace std;

const int N = 20010;

int n, m;

int f[N];

int main() {
    
    cin >> m >> n;
    
    for (int i = 1; i <= n; i ++ ) {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + v);
        }
    }
    
    
    cout << m - f[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

AcWing 1022. 宠物小精灵之收服

代价： v1 精灵球数量， v2 皮卡丘体力值
价值： 收服小精灵的数量
双重代价的 0-1 背包问题

#include 
using namespace std;

const int N = 1010;

int f[N][N];

int V1, V2, w;

int n, m;

int main() {
    
    cin >> V1 >> V2 >> w;
    
    for (int i = 1; i <= w; i ++ ) {
        int v1, v2;
        cin >> v1 >> v2;
        for (int j = V1; j >= v1; j -- ) {
            for (int k = V2; k >= v2; k -- ) {
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
            }
        }
    }
    
    // 得皮卡丘体力小于等于0的野生小精灵不会被小智收服。
    cout << f[V1][V2 - 1] << " ";
    
    
    int j = V2 - 1;
    
    while (j > 0 && f[V1][j - 1] == f[V1][V2 - 1]) j -- ;
    
    cout << V2 - j;
    
    
    
    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

AcWing 278. 数字组合

#include 
using namespace std;

const int N = 10010;

int f[N];

int n, m;

int main() {
    
    cin >> n >> m;
    
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        int v;
        cin >> v;
        for (int j = m; j >= v; j -- ) {
            f[j] += f[j - v];
        }
    }
    
    cout << f[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

AcWing 426. 开心的金明

#include 
using namespace std;

const int N = 30010;

int n, m;
int f[N];

int main() {
    
    cin >> m >> n;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w;
        cin >> v >> w;
        w = v * w;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[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

AcWing 734. 能量石

#include 
using namespace std;

const int N = 10010; 

int n, m, T;
int f[N];

struct Stone{
    int s, e, l;
    bool operator < (const Stone &t) const {
        return s * t.l < l * t.s;
    }
}stone[N];

int main() {
    
    cin >> T;
    int cnt = T;
    while (T -- ) {
        
        cin >> n;
        m = 0;
        for (int i = 1; i <= n; i ++ ) {
            int s, e, l;
            cin >> s >> e >> l;
            stone[i] = {s, e, l};
            m += s;
        }
        
        sort(stone + 1, stone + n + 1);
        memset (f, -0x3f, sizeof f);
        
        f[0] = 0;
        
        for (int i = 1; i <= n; i ++ ) {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            for (int j = m; j >= s; j -- ) {
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
            }
        }
        
        int res = 0;
        
        for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
        
        printf("Case #%d: %d\n", cnt - T, res);
        
    }
    
    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
44
45
46
47
48
49
50
51
52

完全背包问题

AcWing 1023. 买书

方案数转移：设定 f[0] = 1, 当满足条件 - v 时，变可得到 0， 实现方案数量的累加

#include 
using namespace std;

const int N = 1010;

int m;

int v[5] = {0, 10, 20, 50, 100};

int f[N];

int main() {
    
    cin >> m;
    
    f[0] = 1;
    for (int i = 1; i <= 4; i ++ ) {
        for (int j = v[i]; j <= m; j ++ ) {
            f[j] += f[j - v[i]];
        }
    }
    
    
    cout << f[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

AcWing 1021. 货币系统

#include 
using namespace std;

const int N = 3010;
typedef long long LL;

int n, m;

LL f[N];

int main() {
    
    cin >> n >> m;
    
    f[0] = 1;
    for (int i = 1;  i <= n; i ++ ) {
        int v;
        cin >> v;
        for (int j = v; j <= m; j ++ ) {
            f[j] += f[j - v];
        }
    }
    
    cout << f[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

AcWing 532. 货币系统

• 利用完全背包求每个数的方案数后，如果等于 1 ，说明只能被自己所表示，则一定要选出来，组成最小的系统。

#include 
using namespace std;

const int N = 25010;

int f[N], v[N];
int n, T, m;

int main() {
    
    cin >> T;
    while (T -- ) {
        cin >> n;
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) cin >> v[i], m = max(v[i], m);
        
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            for (int j = v[i]; j <= m; j ++ ) {
                f[j] += f[j - v[i]];
            }
        }
        
        int ans = 0;
        for (int i = 1; i <= n; i ++ ) {
            if (f[v[i]] == 1) ans ++;
        }
        
        cout << ans << endl; 
        
    }
    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

多重背包问题

AcWing 6. 多重背包问题 III

• 将多重背包利用二进制优化为 01 背包问题

#include 
using namespace std;

const int N = 2e4 + 10; 
typedef pair<int, int> PII;

int n, m;
int f[N];
vector<PII> G;

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2) {
            s -= k;
            G.push_back({v*k, w*k});
        }
        if (s > 0) G.push_back({v*s, w*s});
    }
    
    for (int i = 0; i <= G.size(); i ++ ) {
        int v = G[i].first, w = G[i].second;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[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

AcWing 1019. 庆功会

#include 
using namespace std;

const int N = 6010;
typedef pair<int, int> PII;

int n, m;

int f[N];

vector<PII> G;

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k < s; k *= 2) {
            s -= k;
            G.push_back({k * v, k * w});
        }
        if (s) G.push_back({s * v, s * w});
    }
    
    for (int i = 0; i < G.size(); i ++ ) {
        int v = G[i].first, w = G[i].second;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[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

混合背包问题

AcWing 7. 混合背包问题

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == -1) {
            for (int j = m; j >= v; j -- ) {
                f[j] = max(f[j], f[j - v] + w);
            } 
        } else if (s == 0) {
            for (int j = v; j <= m; j ++ ) {
                f[j] = max(f[j], f[j - v] + w);
            }
        } else {
            for (int k = 1; k <= s; k *= 2) {
                for (int j = m; j >= k * v; j -- ) {
                    f[j] = max(f[j], f[j - k * v] + k * w);
                }
                s -= k;
            }
            
            if (s) {
                for (int j = m; j >= s * v; j -- ) {
                    f[j] = max(f[j], f[j - s * v] + s * w);
                }
            }
        }
    }
    
    cout << f[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

二维费用的背包问题

AcWing 8. 二维费用的背包问题

#include 
using namespace std;

const int N = 110;

int f[N][N];

int V, M, n;

int main() {
    
    cin >> n >> V >> M;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j -- ) {
            for (int k = M; k >= m; k -- ) {
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
            }
        }
    }
    
    
    cout << f[V][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

AcWing 1020. 潜水员

#include 
using namespace std;

const int N = 100;

int f[N][N];
int V, M, n;

int main() {
    
    cin >> V >> M >> n;
    
    memset (f, 0x3f, sizeof f);
    
    f[0][0] = 0;
    for (int i = 1; i <= n; i ++ ) {
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= 0; j -- ) {
            for (int k = M; k >= 0; k -- ) {
                // 如果超过容量的就用 f[0][0] 这个状态来取，此时一定不会比最小值小
                f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w);
            }
        }
    }
    
    
    cout << f[V][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

分组背包问题

AcWing 1013. 机器分配

#include 
using namespace std;

const int N = 30;

int n, m;
int f[N][N], w[N][N];
int way[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> w[i][j];
        }
    }
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= m; j ++ ) {
            for (int k = 0; k <= m; k ++ ) {
                if (k <= j) f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    
    int j = m;
    for (int i = n; i >= 1; i -- ) {
        for (int k = 0; k <= j; k ++ ) {
            if (f[i][j] == f[i - 1][j - k] + w[i][k]) {
                way[i] = k;
                j -= k;
                break;
            }
        }
    }
    
    for (int i = 1; i <= n; i ++ ) cout << i << " " << way[i] << endl;
    
    
    
    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
44
45
46

背包求方案数

AcWing 11. 背包问题求方案数

#include 
using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n, m;
int f[N], cnt[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 0; i <= m; i ++ ) {
        cnt[i] = 1;
    }
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- ) {
            int value = f[j - v] + w;
            if (f[j] < f[j - v] + w) {
                f[j] = f[j - v] + w;
                cnt[j] = cnt[j - v];
            } else if (f[j] == f[j - v] + w) {
                cnt[j] += cnt[j - v];
            }
            cnt [j] %= mod;
         }
    }
    
    cout << cnt[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

AcWing 12. 背包问题求具体方案

题目要求输出字典序最小的解，假设存在一个包含第 1 个物品的最优解，为了确保字典序最小那么我们必然要选第一个。那么问题就转化成从 $2～N$ 这些物品中找到最优解。之前的 $f(i,j)$ 记录的都是前 $i$ 个物品总容量为 $j$ 的最优解，那么我们现在将 f(i,j) 定义为从第 $i$ 个元素到最后一个元素总容量为 $j$ 的最优解。接下来考虑状态转移：

$$f(i,j)=max(f(i+1,j),f(i+1,j-v[i])+w[i])$$

两种情况，第一种是不选第 $i$ 个物品，那么最优解等同于从第 $i+1$ 个物品到最后一个元素总容量为 $j$ 的最优解；第二种是选了第 $i$ 个物品，那么最优解等于当前物品的价值 $w[i]$ 加上从第 $i+1$ 个物品到最后一个元素总容量为 $j-v[i]$ 的最优解。

计算完状态表示后，考虑如何的到最小字典序的解。首先 $f(1,m)$ 肯定是最大价值，那么我们便开始考虑能否选取第1个物品呢。

如果 $f(1,m)=f(2,m-v[1])+w[1]$，说明选取了第 1 个物品可以得到最优解。

如果 $f(1,m)=f(2,m)$，说明不选取第一个物品才能得到最优解。

如果 $f(1,m)=f(2,m)=f(2,m-v[1])+w[1]$，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。

#include 
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    //逆序做 01 背包问题
    /*
        0 2 4 6 6 8 
        0 0 4 4 6 8 
        0 0 0 4 6 6 
        0 0 0 0 6 6 

    */
    for (int i = n; i >= 1; i -- ) {
        for (int j = 0; j <=m; j ++ ) {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    } 

    int j = m;

    //正序开始，即为结果的开始位置，从f[1][m],开始寻找最优价值构成的物品
    for (int i = 1; i <= n; i ++ ) {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            j -= v[i];
            cout << i << " ";
        }
    }



    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
44