算法基础-背包问题（01背包问题）
本文系统介绍了背包问题及其经典变体，重点解析了01背包问题的解题思路与实现方法。文章首先概述了背包问题的基本形式（在容量限制下选择物品使价值最大）及其六种主要变体（01背包、完全背包、多重背包等），指出01背包是其他变体的基础。通过牛客网例题详细讲解了01背包的两类解法：不要求装满和必须恰好装满的情况，包括状态表示、转移方程、初始化和空间优化技巧。随后展示了三个经典题目（采药、点菜、奶牛飞盘队）的
1.背包问题
01 背包
1.1 01 背包
链接：https://ac.nowcoder.com/acm/problem/226514
来源：牛客网
【解法】
【参考代码】
#include <iostream>
#include <cstring>
using namespace std;
// 常量定义：题目中n/V最大为1000，留10个余量
const int N = 1010;
int main() {
// 1. 变量定义
int n, m; // n=物品数，m=背包最大容量（对应题目中的V）
int v[N], w[N]; // v[i]=第i个物品体积，w[i]=第i个物品价值
int f[N][N]; // 二维dp数组：f[i][j]表示前i个物品、体积≤j的最大价值
// 2. 读取输入
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
// ===================== 第一问：不要求装满 =====================
// 初始化：二维数组默认值为0（未选物品时价值为0）
// 遍历前i个物品
for (int i = 1; i <= n; i++) {
// 遍历所有可能的背包体积（0到m）
for (int j = 0; j <= m; j++) {
// 情况1：不选第i个物品 → 价值 = 前i-1个物品、体积j的价值
f[i][j] = f[i-1][j];
// 情况2：选第i个物品（前提：背包体积≥物品体积）
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
}
}
}
// 输出第一问结果：前n个物品、体积≤m的最大价值
cout << f[n][m] << endl;
// ===================== 第二问：要求恰好装满 =====================
// 初始化：将数组全部设为极小值（-0x3f3f3f3f），代表“无法装满该体积”
memset(f, -0x3f, sizeof f);
f[0][0] = 0; // 唯一合法初始状态：前0个物品、体积0，价值0（恰好装满）
// 遍历前i个物品（逻辑和第一问一致）
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 情况1：不选第i个物品
f[i][j] = f[i-1][j];
// 情况2：选第i个物品（前提：背包体积≥物品体积）
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i-1][j - v[i]] + w[i]);
}
}
}
// 结果判断：若f[n][m]为极小值，说明无法装满，输出0；否则输出f[n][m]
if (f[n][m] < 0) {
cout << 0 << endl;
} else {
cout << f[n][m] << endl;
}
return 0;
}1.2 采药
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1复制
70 3 71 100 69 1 1 2
输出 #1复制
3
说明/提示
【数据范围】
- 对于 30% 的数据，M≤10；
- 对于全部的数据，M≤100。
【题目来源】
NOIP 2005 普及组第三题
【解法】
【参考代码】
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int t[N], w[N];
int f[N];
int main()
{
cin >> m >> n;
for(int i = 1; i <= n; i++) cin >> t[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = m; j >= t[i]; j--) // 修改遍历顺序
{
f[j] = max(f[j], f[j - t[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}1.3 ⼩ A 点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩 M 元 (0<M≤10000)。
餐馆虽低端，但是菜品种类不少，有 N 种 (1≤N≤100)，第 i 种卖 ai 元 (0<ai≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 1 秒。
输入格式
第一行两个整数 N 和 M，分别表示菜品种类和 uim 身上的钱数。
第二行 N 个正整数 ai（可能有重复），用空格隔开，分别表示每种菜的价格。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 [0,231−1] 之内（不超过 C/C++的 int 范围）。
输入输出样例
输入 #1复制
4 4 1 1 2 2
输出 #1复制
3
说明/提示
2020.8.29，增添一组 hack 数据 by @yummy
【解法】
【参考代码】
#include<iostream>
#include<cstring>
using namespace std;
const int V=1010;
int n, m;
int a[110];
int f[V]; // 一维数组：f[j]表示凑出体积j的方案数
int main() {
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
f[0] = 1; // 初始化：凑0体积的方案数=1
for(int i=1; i<=n; i++) {
for(int j=m; j>=a[i]; j--) { // 倒序遍历，避免重复选
f[j] += f[j - a[i]];
}
}
cout << f[m] << endl;
return 0;
}3.1.4 Cow Frisbee Team
题目描述
老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 N 头奶牛中选出一支队伍。
每只奶牛的能力为整数，第 i 头奶牛的能力为 Ri。飞盘队的队员数量不能少于 1、大于 N。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信，他的幸运数字是 F，所以他要求队伍的总能力必须是 F 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 108 取模的值。
输入格式
第一行：两个用空格分开的整数：N 和 F。
第二行到 N+1 行：第 i+1 行有一个整数 Ri，表示第 i 头奶牛的能力。
输出格式
第一行：单个整数，表示方案数对 108 取模的值。
输入输出样例
输入 #1复制
4 5 1 2 8 2
输出 #1复制
3
说明/提示
对于 100% 的数据，1≤N≤2000，1≤F≤1000，1≤Ri≤105。
【解法】
【参考代码】
#include <iostream>
using namespace std;
// 常量定义：
// N：奶牛数量上限（题目N≤2000，留10余量）
// M：F的上限（题目F≤1000，留10余量）
// MOD：取模值（10^8）
const int N = 2010, M = 1010, MOD = 1e8;
int main() {
int n, F; // n=奶牛数，F=幸运数字（避免用m，和模数混淆）
int R[N]; // R[i]存储第i头奶牛的能力值
// dp[i][j]：前i头奶牛中选，总和%F=j的组合数
long long dp[N][M]; // 用long long避免中间结果溢出
// 初始化dp数组为0（避免随机值干扰）
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dp[i][j] = 0;
}
}
// 1. 读取输入
cin >> n >> F;
for (int i = 1; i <= n; i++) {
cin >> R[i];
// 提前计算能力值的模F结果，减少后续计算量
R[i] = R[i] % F;
}
// 2. 动态规划初始化：选0头奶牛，总和为0，模F=0，仅1种方案
dp[0][0] = 1;
// 3. 状态转移：遍历每头奶牛，计算所有余数的组合数
for (int i = 1; i <= n; i++) {
for (int j = 0; j < F; j++) {
// 情况1：不选第i头奶牛 → 组合数 = 前i-1头凑余数j的数量
dp[i][j] = dp[i-1][j];
// 情况2：选第i头奶牛 → 需前i-1头凑余数 (j - R[i]) mod F
// 修正负数：(j - R[i] + F) % F 确保结果在0~F-1之间
int pre_j = (j - R[i] + F) % F;
dp[i][j] = (dp[i][j] + dp[i-1][pre_j]) % MOD;
}
}
// 4. 计算结果：总组合数 - 选0头的无效方案（确保非负）
long long ans = (dp[n][0] - 1 + MOD) % MOD;
cout << ans << endl;
return 0;
}
火山引擎开发者社区是火山引擎打造的AI技术生态平台，聚焦Agent与大模型开发，提供豆包系列模型（图像/视频/视觉）、智能分析与会话工具，并配套评测集、动手实验室及行业案例库。社区通过技术沙龙、挑战赛等活动促进开发者成长，新用户可领50万Tokens权益，助力构建智能应用。
更多推荐
24
0- 0
已为社区贡献1条内容
所有评论(0)