背包模型题目

[NOIP2005 普及组] 采药

题目描述

https://www.luogu.com.cn/problem/P1048open in new window

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$ （ $1 \le T \le 1000$ ）和 $M$ （ $1 \le M \le 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 $30\%$ 的数据， $M \le 10$ ；
对于全部的数据， $M \le 100$ 。

思路

显然是01背包模版题目

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> m >> n;
    vector<int> f(m + 1);
    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]<<endl;


    return 0;
}

[NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 $V$ ，同时有 $n$ 个物品，每个物品有一个体积。

现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 $V$ ，表示箱子容量。

第二行共一个整数 $n$ ，表示物品总数。

接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $100\%$ 数据，满足 $0<n \le 30$ ， $1 \le V \le 20000$ 。

思路

题目说要求剩余体积最小，意思就是要让我们求装进去的体积最大，但是这里和01背包问题相比少了一个变量（01背包问题是体积和价值）

在这里，可以将价值看成体积，体积看成体积即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n,m;
    cin>>m>>n;
    vector<int> f(m+1);
    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]<<endl;
    return 0;
}

宠物小精灵之收服

题目

链接：https://www.acwing.com/problem/content/1024/open in new window

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。

小智也想收服其中的一些小精灵。

然而，野生的小精灵并不那么容易被收服。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。

如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。

请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围

$0 < N \le 1000$ ,
$0 < M \le 500$ ,
$0 < K \le 100$

输入样例1：

输出样例1：

3 30

输入样例2：

输出样例2：

0 100

思路

本题为二维费用背包问题：

花费1：精灵球数量

花费2：皮卡丘的体力值

价值：小精灵的数量

二维费用背包问题：

状态表示：f[i,j,k]表示从前i个精灵中选，且花费1不超过j,花费2不超过k的选法的最大价值

状态计算：f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+1)

最多收服的小精灵数量：f[K,N,M]

f[j][k]表示前i个小精灵，精灵球为j,体力值为k时最多收服的小精灵数量

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1010;
int f[N][N];


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = n; j >= v; j--) {
            for (int t = m - 1; t >= w; t--) {
                f[j][t] = max(f[j][t], f[j - v][t - w] + 1);
            }
        }
    }
    cout << f[n][m - 1] << " ";
    for (int i = 0; i <= m; i++) {
        if (f[n][m - 1] == f[n][i]) {
            cout << m - i << endl;
            break;
        }
    }
    return 0;
}

数字组合

题目

链接：https://www.acwing.com/problem/content/280/open in new window

给定 $N$ 个正整数 $A_1,A_2,…,A_N$ ，从中选出若干个数，使它们的和为 $M$ ，求有多少种选择方案。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

第二行包含 $N$ 个整数，表示 $A_1,A_2,…,A_N$

输出格式

包含一个整数，表示可选方案数。

数据范围

$1 \le N \le 100$ ,
$1 \le M \le 10000$ ,
$1 \le A_i \le 1000$ ,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2

输出样例：

思路

动态规划：

状态表示：f[i,j]表示所有从前i个物品中选，且总价值恰好是j的方案个数
状态计算：
- 不包括物品i的所有选法：f[i-1,j]
- 包括物品i的所有选法：f[i-1,j-vi]
状态转移方程：f[i,j]=f[i-1,j]+f[i-1,j-vi]

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1);
    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]<<endl;

    return 0;
}

或者采用01背包恰好装满背包求方案数的模版代码：

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1, -INT_MAX), c(m + 1);
    c[0] = 1;
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        for (int j = m; j >= v; j--) {
            if (f[j - v] + v > f[j]) {
                f[j] = f[j - v] + v;
                c[j] = c[j - v];
            } else if (f[j] == f[j - v] + v) {
                c[j] += c[j - v];
            }
        }
    }
    cout << c[m] << endl;

    return 0;
}

庆功会

题目

链接：https://www.acwing.com/problem/content/1021/open in new window

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

输入格式

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

输出格式

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

数据范围

$n \le 500, m \le 6000$
$v \le 100, w \le 1000, s \le 10$

输入样例：

输出样例：

思路

多重背包问题模版：

不需要优化，时间复杂度为 $500*60000*10=3e7$

动态规划：

状态表示：f[i,j]表示考虑前 i 个物品，且总体积不超过 j 的集合下能获得的最大价值。
状态计算：f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);选第i个物品和不选第i个物品

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1);
    for (int i = 1; i <= n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = m; j >= v; j--) {
            for (int k = 0; k <= s; k++) {
                if (j >= k * v)
                    f[j] = max(f[j], f[j - k * v] + k * w);
            }
        }
    }
    cout << f[m] << endl;


    return 0;
}

买书

题目

题目链接：https://www.acwing.com/problem/content/1025/open in new window

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式

一个整数 n，代表总共钱数。

输出格式

一个整数，代表选择方案种数。

输入样例1：

输出样例1：

思路

完全背包问题：

动态规划：

状态表示：f[i,j]表示所有从前i个物品中选，且总体积恰好是j的方案

状态计算：

f[i,j] = f[i-1,j]+f[i-1,j-v*1]+f[i-1.j-v*2]+...+f[i-1,j-v*s]
f[i,j-v]= f[i-1,j-v*1]+f[i-1,j-v*2]+...+f[i-1,j-v*s]

可以得出：f[i,j]=f[i-1,j]+f[i,j-v]

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n;
    cin >> n;
    int v[5] = {0, 10, 20, 50, 100};
    vector<int> f(n + 1);
    f[0] = 1;
    //fi表示价格不超过i的选法的个数
    for (int i = 1; i <= 4; i++) {
        for (int j = v[i]; j <= n; j++) {
            f[j] += f[j - v[i]];
        }
    }
    cout << f[n] << endl;

    return 0;
}

潜水员

题目

题目链接：https://www.acwing.com/problem/content/1022/open in new window

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

第一行有2个整数 m，n 。它们表示氧，氮各自需要的量。

第二行为整数 k 表示气缸的个数。

此后的 k 行，每行包括ai，bi，ci ，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。

输出格式

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

思路

动态规划：

状态表示：f[i,j,k]表示所有从前i个物品中选，且氧气含量至少是j,氮气含量至少是k的所有选法的最小值
状态计算：
- 所有不包含物品i的所有选法：f[i - 1,j,k]
- 所有包含物品i的所有选法：f[i - 1,j - v1,k - v2]

问题：

二维费用的背包问题的状态转移方程：

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);

本题的状态转移方程：

for(int j = V;j >= 0;j --)
    for(int k = M;k >= 0;k --)
        f[j][k] = min(f[j][k], f[max(0, j - v)][max(0, k - m)] + w);

原因：本题求的至少需要体积V，重量M的情况下，能拿到价值的最小值。就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如f[3][5]，至少需要3个体积，5个重量，求能拿到价值的最小值，现在只有一个物品，体积是4，重量是4，价值w，它说至少需要3个体积，那么体积是4还是可以用到，只是多了1个体积没用占着而已，不影响其价值。因此若用了这个物品，则变成了求f[0][1] + w，表示体积已经不再需求了，只需要0个体积即可

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;
int f[30][100];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    int s;
    cin >> s;
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    while (s--) {
        int a, b, c;
        cin >> a >> b >> c;
        for (int j = n; j >= 0; j--) {
            for (int k = m; k >= 0; k--) {
                f[j][k] = min(f[j][k], f[max((int) 0, j - a)][max((int) 0, k - b)] + c);
            }
        }
    }
    cout << f[n][m];


    return 0;
}

背包模型题目

# [NOIP2005 普及组] 采药

# 题目描述

# 输入格式

# 输出格式

# 样例 #1

# 样例输入 #1

# 样例输出 #1

# 提示

# 思路

# 代码

# [NOIP2001 普及组] 装箱问题

# 题目描述

# 输入格式

# 输出格式

# 样例 #1

# 样例输入 #1

# 样例输出 #1

# 提示

# 思路

# 代码

# 宠物小精灵之收服

# 题目

# 输入格式

# 输出格式

# 数据范围

# 输入样例1：

# 输出样例1：

# 输入样例2：

# 输出样例2：

# 思路

# 代码

# 数字组合

# 题目

# 输入格式

# 输出格式

# 数据范围

# 输入样例：

# 输出样例：

# 思路

# 代码

# 庆功会

# 题目

# 输入格式

# 输出格式

# 数据范围

# 输入样例：

# 输出样例：

# 思路

# 代码

# 买书

# 题目

# 输入格式

# 输出格式

# 输入样例1：

# 输出样例1：

# 思路

# 代码

# 潜水员

# 题目

# 输入格式

# 输出格式

# 思路

# 代码

[NOIP2005 普及组] 采药

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

思路

代码

[NOIP2001 普及组] 装箱问题

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

思路

代码

宠物小精灵之收服

题目

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

思路

代码

数字组合

题目

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路

代码

庆功会

题目

输入格式

输出格式

数据范围

输入样例：

输出样例：

思路

代码

买书

题目

输入格式

输出格式

输入样例1：

输出样例1：

思路

代码

潜水员

题目

输入格式

输出格式

思路

代码