背包系列的题目（算法基础课，算法提高课）：
（1）01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
cin >> n >> m;
//f[0][0-m],从前0件物品开始选,体积不超过m的最大值默认是0
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; 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]);
}
}
cout << f[n][m] << endl;
return 0;
}
//有优化版
/*
1. f[i] 仅用到了f[i-1]层,
2. j与j-v[i] 均小于j
3.若用到上一层的状态时,从大到小枚举, 反之从小到大哦
*/
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j-v[i]]+w[i]);
cout << f[m] << endl;
return 0;
}
(2)装箱问题(01背包问题延伸 体积价值相同)
有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
第一行是一个整数 V，表示箱子容量。
第二行是一个整数 n，表示物品数。
接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。
输出格式
一个整数，表示箱子剩余空间。
数据范围
0<V≤20000,
0<n≤30
输入样例：
24
6
8
3
12
7
9
7
输出样例：
0
//01背包，体积就是价值
#include<iostream>
#include<algorithm>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 20010;
int n, m;
int f[M];
int main()
{
cin >> m >> n;
for (int i = 0; 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;
}
（3）数字组合
给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示 A1,A2,…,AN。
输出格式
包含一个整数，表示可选方案数。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。
输入样例：
4 4
1 1 2 2
输出样例：
3
分析
对于本题我们可以把每个 正整数 看作是一个 物品
正整数 的值就是 物品 的 体积
我们方案选择的 目标 是最终 体积 恰好为 mm 时的 方案数
于是本题就变成了 01背包求解方案数 的问题了
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
f[0] = 1;
for (int i = 0; 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;
}
总结：集合：考虑前i个正整数，且当前总和恰好为j的方案，属性为方案数，未优化：f[i][j]=f[i-1][j]+f[i-1][j-v[i]],优化成一维。
(4)二维费用的背包问题
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8
代码：
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 110;
int f[N][N];
int n,m,w;
int main()
{
cin>>n>>m>>w;
for(int i=1;i<=n;i++)
{
int v1,m1,w1;
cin>>v1>>m1>>w1;
for(int j =m;j>=v1;j--)
{
for(int k=w;k>=m1;k--)
{
f[j][k]=max(f[j][k],f[j-v1][k-m1]+w1);
}
}
}
cout<<f[m][w];
return 0;
}
(5)宠物小精灵之收服
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？
输入格式
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出格式
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
数据范围
0<N≤1000,
0<M≤500,
0<K≤100
输入样例1：
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例1：
3 30
输入样例2：
10 100 5
8 110
12 10
20 10
5 200
1 110
输出样例2：
0 100
代码：
//体积1：精灵球的数量
//体积2：皮卡丘的体力值
//价值： 抓到的小精灵的数量
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 510;
int n, V1, V2;
int f[N][M];
int main()
{
cin >> V1 >> V2 >> n;
for (int i = 0; i < n; i ++ )
{
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j -- )
for (int k = V2 - 1; k >= v2; k -- )
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
cout << f[V1][V2 - 1] << ' ';
int k = V2 - 1;
while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k -- ;
cout << V2 - k << endl;
return 0;
}
总结：两个体积，一个价值
(6)潜水员
潜水员为了潜水要使用特殊的装备。
他有一个带2种气体的气缸：一个为氧气，一个为氮气。
让潜水员下潜的深度需要各种数量的氧和氮。
潜水员有一定数量的气缸。
每个气缸都有重量和气体容量。
潜水员为了完成他的工作需要特定数量的氧和氮。
他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围
1≤m≤21,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249
难度：简单
时/空限制：1s / 64MB
总通过数：4728
总尝试数：9061
来源：《信息学奥赛一本通》
算法标签
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 85;
int n, m, t;
int v1[N], v2[N], w[N];
int f[M][M];
int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= t; ++ i) cin >> v1[i] >> v2[i] >> w[i];
memset(f, 0x3f, sizeof f); //求最小值要把除初始状态以外的所有状态初始化为+∞
f[0][0] = 0; //这里我们把所有j,k小于0的初始状态都合并到f[0][0][0]中来转移,也就是下面的max操作
for (int i = 1; i <= t; ++ i)
{
for (int j = n; j >= 0; -- j)
{
for (int k = m; k >= 0; -- k)
{
f[j][k] = min(f[j][k], f[max(j - v1[i], 0)][max(k - v2[i], 0)] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
作者：彩色铅笔
链接：https://www.acwing.com/solution/content/53848/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
**总结：
分析
本题是一个 二维费用01背包问题 ，但和一般的 二维费用01背包问题 不同
这题要求的是 费用不少于 规定条件，因此我们需要对于 状态的定义 进行改变
从1-i中选，氧气体积至少是j，氮气含量至少是k， （至少至少至少），不是恰好也不是至多
DP如果只有一个起点，那除起点外都要初始化，如果任意状态都可以作为起点，则无需初始化。
这也是我dp分析里经常加入初始状态和目标状态的原因
这是我判断是否要初始化状态的根据
然后关于初始化是什么，是题目而定，目的是为了避免非起点的转移影响目标状态的值
这题：初始状态：f[0][j][k] 其中 j,k≤0j,k≤0
然后这题比较特殊，把所有小于 0 的状态合并到 0 进行转移
所以起点只有 f[0][0]
因为j-v就算是负数也满足题意，满足至少是9的也满足至少是-2的，故不需要j>v;但满足越界性，设为0即可**
(7) 开心的金明
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。
今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。
于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。
他还从因特网上查到了每件物品的价格（都是整数元）。
他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为：
v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]
请你帮助金明设计一个满足要求的购物单。
输入格式
输入文件的第 1 行，为两个正整数 N 和 m，用一个空格隔开。（其中 N 表示总钱数，m 为希望购买物品的个数）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v 和 p。（其中 v 表示该物品的价格，p 表示该物品的重要度）
输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 108）。
数据范围
1≤N<30000,
1≤m<25,
0≤v≤10000,
1≤p≤5
输入样例：
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例：
3900
代码：
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N = 3e5 + 10;
int n, m;
int f[N];
int main()
{
cin >> m >> n;
for (int i = 0; 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*v);
}
cout << f[m] << endl;
return 0;
}
总结：01背包模型，求得值不同而已
