背包问题
01背包问题 ->
完全背包问题 ->
多重背包问题I ->
多重背包问题II
各问题求方案数
- 01背包
->
分组背包 - 01背包
+
完全背包+
多重背包I->
混合背包 - 01背包
->
二维背包
- 多重背包包I
+
二进制优化->
多重背包问题II - 多重背包I
+
单调队列+
滑动窗口求最值->
多重背包III - 树形DP
+
分组背包->
有依赖背包问题
01背包问题:所有物品只能选一次
完全背包问题:所有物品能选择次数不上限
多重背包问题I:每个物品选择的次数都有限且不一样
多重背包问题II:通过二进制法压缩v,w,大量减少循环数量
多重背包问题III:通过单调队列和滑动窗口进行优化
分组背包问题:物品选择次数不一样,且同组物品只能选一次
混合背包问题:
n种物品体积v,第一类物品只能用1次(01背包);第二类物品可以用无限次(完全背包);第三类物品最多只能用 si 次(多重背包);每种体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。
有依赖背包问题:物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点,这是一道很好的题。
二维背包:一般是求二维消费问题,多一维就多一轮体积循环
代码模版
一个基本思维:
for 物品
for 背包
for 决策
另外在状态转移中,如果是从f[i-1]
转移过来的要从大到小循环,从f[i]
转移过来的要从小到大循环
一个技巧是:只有完全背包是从小到大循环,其他都是从大到小循环
核心思维是要保证状态转移过来的量是已经计算过的量。
如果是求方案数的话,状态转移的max, min
之类的改为+=
比如说在买书方案中,f[j] = max(f[j], f[j-v])
变为f[j] += f[j-v]
关于背包问题的关键变形之 ---- 把不超过容积V的条件改为
1.刚好为容积V。(数字组合) 2.至少为容积V(潜水员那道题)
的技巧写在代码模版的最后,记得看一下
模版1. 01背包问题
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. 二维费用背包问题
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;v <= j;j --)
for(int k = M;m <= k;k--)
f[j][k] = max(f[j][k], f[j-v][k-m]+w);
}
cout << f[V][M];
return 0;
}
模版3. 完全背包
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 = v[i]; j <= m; j ++ ) // 和01只有这里不一样
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
模版4. 多重背包问题 O(nms)
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
//s[i]存的是物品的数量,保证体积小于背包按数量遍历就行
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
cout << f[n][m] << endl;
return 0;
}
模版5. 多重背包问题II
用2^0^,2^1^,2^2^…2^k^全排列组合,可以表示2^(k+1)^-1
利用这一点压缩背包,转换成01背包问题
const int N = 12*1010, M = 2010; //N要算1000log2000
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++ ) //处理二进制优化
{
int vi, wi, s;
cin >> vi >> wi >> s;
int k = 1; // 2^0,算二进制倍数的
while(k <= s) //一直算到 2^k <= s 的情况
{
cnt++; //下标
v[cnt] = vi * k; //二进制化的体积和价值
w[cnt] = wi * k;
s -= k; //减去二进制化的k
k *= 2; //2^(k+1)
}
if(s > 0) //如果还有剩余的话,即c,就加上
{
cnt++;
v[cnt] = vi * s;
w[cnt] = wi * s;
}
}
n = cnt; //记得更新一下n
//然后做一遍01背包问题
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;
}
模版6. 多重背包问题III
我他妈没看懂啊啊啊啊啊啊呜呜呜呜我没学明白啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊看不懂啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
int n, m;
int f[N], g[N], q[N];
int main()
{
cin >> n >> m;
for(int i = 0;i < n; i++)
{
int v,w,s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f); //把上一次的滚动数组存下来
for(int j = 0; j < v; j++)
{
int hh = 0, tt = -1; //定义一下单调队列
for(int k=j; k <=m; k += v)
{
if(hh <= tt && q[hh] < k - s*v) hh ++;
//如果队列不空的话求窗口最大值
if(hh <= tt) f[k] = max(f[k],g[q[hh]] + (k-q[hh])/v *w);
while(hh <= tt && g[q[tt]]-(q[tt]-j)/v*w <= g[k] - (k-j)/v*w) tt--;
q[++tt] = k;
}
}
}
cout << f[m] << endl;
return 0;
}
模版7. 分组背包
int main()
{
cin >> n >> m;
for(int i = 1; i<=n ; i ++ )
{
cin >> s[i];
for(int j=0; j < s[i]; j ++ )
cin >> v[i][j] >> w[i][j];
}
for(int i =1;i <= n; i++)
for(int j = m; j >=0;j--)
for(int k = 0; k < s[i]; k++) //遍历组里所有物品
if(v[i][k] <= j) //第i组的第k个物品小于j就放进去试试
f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}
模版8. 混合背包问题 AcWing 7. 混合背包问题
输入格式
第一行两个整数 N,V
用空格隔开,分别表示物品种数和背包容积。
接下来有N
行,每行三个整数 vi,wi,si
,用空格隔开,分别表示第 i
种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次;
si=0 表示第 i 种物品可以用无限次;
* si>0 表示第 i 种物品可以使用 si 次;
输出格式
输出一个整数,表示最大价值。
const int N = 1010;
int n, m;
int f[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ )
{
int v,w,s;
cin >> v >> w >> s;
if(s == 0) //完全背包
for(int j = v; j <= m; j ++ ) f[j] = max(f[j], f[j-v]+w);
else
{
if(s == -1) s=1; //01背包问题是一种特殊的多重背包问题,即s为1
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] << endl;
return 0;
}
模版9. 有依赖的背包问题(树形dp + 深搜 + 分组背包) AcWing 10
f[u,j]
表示所有从以u为根的子树中选,且总体积不超过j
的方案
分组是按体积分的,把每个子树看成是一个物品组,每个物品组里有m+1
个物品(用来表示体积0~m
),体积是i
,价值是f[u][i]
所以就是说对于根节点,他有子树的数目个物品组,我们要在每个子树中选择一个对应的体积的选择,即m+1
个物品中的一种物品, 每个子树都选一个体积出来
题目描述
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系,且依赖关系组成一棵树的形状。如果选择一个物品,则必须选择它的父节点。
每件物品的编号是 i
,体积是 v~i~,价值是 w~i~,依赖的父节点编号是 p~i~。物品的下标范围是 1…N
。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品个数和背包容量。
接下来有 N 行数据,每行数据表示一个物品。
第 i 行有三个整数 v~i~,w~i~,p~i~,用空格隔开,分别表示物品的体积、价值和依赖的物品编号。
如果 p~i~=−1,表示根节点。 数据保证所有物品构成一棵树。
输出格式
输出一个整数,表示最大价值。
数据范围
1≤N,V≤100
1≤vi,wi≤100
父节点编号范围:
内部结点:1≤pi≤N;
根节点 pi=−1;
输入样例:
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例:
11
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int h[N], e[N], ne[N], idx;
int f[N][N];
int v[N], w[N];
//存数的模板
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
//对根节点深搜
void dfs(int u)
{
//分组背包 之 循环物品组
for(int i = h[u]; i != -1; i = ne[i]) //首先遍历u的所有子树
{
int son = e[i];
dfs(e[i]);
// 分组背包 之 循环体积
for(int j = m - v[u]; j >= 0; j --)
for(int k = 0; k <= j;k ++ )//循环决策,讨论当前子树们用多少体积最合适
f[u][j] = max(f[u][j], f[u][j-k] + f[son][k]);//子节点已经都求好了
//体积为k,从son子节点中选,价值就是f[son][k]
}
//将物品u加进去,这里是处理依赖的分支
//如果选择根节点u,那么就有值,值是把根节点加进去
for(int i = m; i >= v[u];i --) f[u][i] = f[u][i-v[u]] + w[u];
//不选的话子节点就都不能选了,依赖就体现在这里
for(int i = 0; i < v[u]; i ++) f[u][i] = 0;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
int root;
for(int i = 1;i <= n; i ++ )
{
int p; // 每个点依赖的点是谁
cin >> v[i] >> w[i] >> p;
if( p == -1 ) root = i;//p为-1时为根节点
else add(p, i); //把依赖的节点加到根节点
}
dfs(root); //从根节点开始递归操作
//f[root][m]表示考虑整颗树的情况下体积不超过m的情况
cout << f[root][m] << endl;
return 0;
}
模版10. 背包问题求具体方案 acwing 12
以01背包为例,输出01背包问题中字典序最小的方案,这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N
思路是在状态转移 f[i][j] = max(f[i-1][j], f[i-1][j-vi])
后判断一下f[i][j]
和哪个状态相等,然后再转一下这个新状态
也可再开个数组记录选择状态,那就不用反推了
y总做法:https://www.acwing.com/activity/content/code/content/119629/
//字典序最小可以用贪心思考:1.只能选 2.只能不选 3.可选可不选->一定要选
//以下两个main()选一个记就行
int main()
{
cin >> n >> m;
//先把v和w都读进来
for(int i = 1; i <= n ; i ++ ) cin >> v[i] >> w[i];
//然后倒着求方案
for(int i = n; i >= 1; i--)
for(int j = 0; j <= m ;j ++ ) //j要从0到m都求
{
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]);
}
//此时f[1][m]是最大值
int j = m;
for(int i = 1; i <= n; i ++ )
{
if(j >= v[i] && f[i+1][j-v[i]]+w[i]==f[i][j])
{
cout << i << ' ';
j-= v[i];
}
}
return 0;
}
int main()
{
cin >> n >> m;
for(int i=n;i>=1;i--)cin>>v[i]>>w[i];
//这里把v数组和w数组倒置了,因为题目要求字典序最小,
//其实就是物品选择方案皆为最大价值时,有物品编号更在前者优先,
//那么把原数组倒置后,从后往前递推时,以字典序最大为策略输出原来的映射就行
for(int i = 1; i <= n; i ++ )
{
for(int j = 0; j <= m; j ++ ) //这里要从0开始,不能从v[i]开始
{
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[n][m]是价值最大
for(int i = n; i >= 1; i -- ) //倒推结果
{
if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i])
{
cout << n - i + 1 << ' '; //第i个物品对应本来的第n-i+1个物品
j -= v[i];
}
}
}
模版11. 二维费用的背包问题
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;v <= j;j --)
for(int k = M;m <= k;k--)
f[j][k] = max(f[j][k], f[j-v][k-m]+w);
}
cout << f[V][M];
return 0;
}
模版12. 体积条件变化情况的探讨
这类题没有一个统一模版,都要具体问题具体分析,但也有一定的规律如下:
1. 背包体积最多是j --> 状态函数 f 全部初始化为0,保证状态转移时体积v >= 0 (有的题也会有初始化1的时候,如买书)--> 状态方程就是正常的模板
2. 背包体积恰好是j --> 状态函数 f[0] = 状态0的实际意义,有时候1有时候0; f[i] = +INF/-INF/0, 也是根据实际意义看,同时保证状态转移时体积v >= 0
--> 状态方程是f[j] = max(f[j],f[j-v]) 根据题目需要变形
最后还要把f从头到尾枚举一遍取 res=max(res, f[i])
3. 背包体积至少是j --> 状态函数 f[0] = 状态0的实际意义,有时候1有时候0; f[i] = +INF/-INF/0, 也是根据实际意义看,状态转移时体积是可以小于0的
体积小于0意味着在消费循环中 for(int j = m; j > vi;j --)中的条件 j > vi 改为 j > 0
例题相关性索引:
01背包问题:采药,开心的金明,+
贪心=
能量石,装箱问题,+
方案数=
数学组合,+
阅读理解+
二维费用=
小精灵
完全背包:+
二维=
潜水员,+
方案数=
买书&
货币系统+
贪心->
货币系统
多重背包问题:庆功会
分组背包:机器分类
-
01背包问题及其(贪心/方案数)衍生
AcWing 423. 采药(普通01背包问题)
这道题是朴素应用,比较裸,没啥好说的
题意:采药有价值,花费时间,时间有限,使价值最大
输入格式
总共时间T秒,共M柱草药,
接下来的 M 行每行包括两个整数,表示采摘某株草药的时间和这株草药的价值。
输出格式
输出文件包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。
数据范围
1≤T≤1000, 1≤M≤100
输入样例:
70 3
71 100
69 1
1 2
输出样例:
3
// 不过竟然可以边读数据边求背包啊,学到了!
int main()
{
cin >> T >> m;
for(int i = 1; i <= m; i ++ )
{
int v, w;
cin >> v >> w;
for( int j = T; v <= j; j--)
f[j] = max(f[j], f[j-v] + w);
}
cout << f[T] << endl;
return 0;
}
AcWing 426. 开心的金明(朴素01,价格按题意变形)
一个简单的01,价格等于体积乘重要度
金明有N元钱,他把想买的东西重要度分为1~5级,每个物品也有自己的真实价值
求N元内能购买的 重要度*物品价值 的最大和
输入格式
输入文件的第 1 行,为两个正整数 N 和 m,用一个空格隔开。(其中 N 表示总钱数,m 为希望购买物品的个数)
从第 2 行到第 m+1 行,第 j 行给出了编号为 j−1 的物品的基本数据,每行有 2 个非负整数 v 和 p。(其中 v 表示该物品的价格,p 表示该物品的重要度)
输出格式
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(数据保证结果不超过 10^8^)。
数据范围
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
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*v); //状态转移根据题意改
}
cout << f[m] << endl;
return 0;
}
AcWing 1024. 装箱问题 (普通01背包,体积变价值等效应用)
箱子容量V,n个物品,每个物品一个体积,求剩余空间最小。
这个题没有直接给价值,但实际上把体积看成价值就可以了
输入格式
第一行是一个整数 V,表示箱子容量。第二行是一个整数 n,表示物品数。
接下来 n 行,每行一个正整数(不超过10000),分别表示这 n 个物品的各自体积。
输出格式
一个整数,表示箱子剩余空间。
数据范围
0<V≤20000, 0<n≤30
输入样例:
24
6
8
3
12
7
9
7
输出样例:
0
int main()
{
cin >> V >> n;
for(int i = 1; i <= n; i++)
{
int v;
cin >> v;
for(int j = V; v<=j; j--)
f[j] = max(f[j], f[j-v]+v);
}
int res = V-f[V]; //输出的是剩余空间
cout << res << endl;
return 0;
}
AcWing 1022. 宠物小精灵之收服(二维消费的01背包问题,且消费边界特判)
主要是题又臭又长,按链接读题,
大概题意是 给定精灵球数量,皮卡丘体力;给定每个精灵消耗精灵球和体力,求最多抓捕数
https://www.acwing.com/problem/content/1024/
精灵球和皮卡丘体力是二维花费,要开多一维f来表示
价值是小精灵数量,让数量最大就是价值最大
f[i,j,k]
表示前i个物品中,花费v1不超过j,花费v2不超过k的选法最大价值
f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+1)
每多一维消费就给f[N]
加一维,用来记录新体积,然后再加一重消费循环即可,还是比较好理解的
输入格式
输入数据的第一行包含三个整数:N,M,K,分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出格式
输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R
数据范围
0<N≤1000 ,
0<M≤500,
0<K≤100
输入样例:
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例:
3 30
#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 = 1; i <= n; i ++ )
{
//耗费精灵球,耗费体力
int v1,v2;
cin >> v1 >> v2;
for(int j = V1; j >= v1; j--)
for(int k = V2-1; k >= v2; k--)/ /皮卡丘体积大于等于0,所以是V2-1
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;
}
AcWing 278. 数字组合(01背包变形之–背包体积恰好等于j)
这题要求和刚好为M,和就是体积,也就是体积刚好等于M的方案数。
给N个正整数 A~1~, A~2~, …, A~N~ 从中选出若干个数,使它们的和为 M,求有多少种选择方案
输入格式
第一行包含两个整数 N 和 M。第二行包含 N 个整数,表示 A~1~, A~2~, …, A~N~。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤N≤100 ,
1≤M≤10000,
1≤Ai≤1000,
输入样例:
4 4
1 1 2 2
输出样例:
3
状态转移f[i][j] = f[i-1][j]+f[i-1][j-v]
f[i][j]
是前i个物品中,体积为j的方案
f[i-1][j]
是前i-1
个物品中,体积为j
的方案,也就是不包含第i
个物品
f[i-1][j-v]
是前i
个物品中,包含第i
个物品的方案
int main()
{
cin >> n >> m;
//空集的情况下体积为1,2,3... 的选法都为0
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;
}
AcWing 1020. 潜水员(01背包变形之–二维背包消费至少为n,m)
需要一定量的氧氮,给定气缸信息,求最小气缸重量
需要的氧氮体积最小为n,m
状态表示:氧氮体积最小为j,k的最小气缸重量
输入格式
第一行有2个整数 m,n。它们表示氧,氮各自需要的量。
第二行为整数 k 表示气缸的个数。
此后的 k 行,每行包括a~i~,b~i~,c~i~,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
const int M = 22, N=80; //氧气背包范围21,氮气背包范围79
int n, m;
int f[M][N];
int main()
{
//氧气需要n,氮气需要m
cin >> n >> m;
int K;
cin >> K;//气缸个数,按个数遍历
memset(f, 0x3f, sizeof f); //之后是取最小值,这里设成正无穷,且不知道缸信息的情况下重量就应是正无穷
f[0][0] = 0;//氧气氮气都需要0时,需要0重量的气缸
for(int i = 0; i < K; i ++ ) //遍历所有气缸
{
int ai, bi, ci;
//氧气ai,氮气bi,缸重量ci
cin >> ai >> bi >> ci;
for(int j = n; j >= 0; j--)
for(int k = m; k >= 0; k--)
{
//负数的情况代表气缸的氮氧含量大于需要的,所以负数是有意义的
//但负数会越界,所以和0取max
f[j][k] = min(f[j][k], f[max(0,j-ai)][max(0,k-bi)]+ci);
}
}
cout << f[n][m] << endl;
return 0;
}
AcWing 11. 背包问题求方案数(用最短路径思想求01背包方案数)
求01背包最优选法的方案数。注意答案可能很大,请输出答案模 10^9^+7 的结果
本质上来说所有dp问题都可以转化为最短路问题
把所有状态看成点,那么重点就是点(n, m)
,起点是(0, 0)
,所有点构成拓扑图
求最优解方案数等于求最短路径条数,当前点的最短路径条数等于上一个点到这个点的最短路径的条数和
g[i,j]
表示f[i,j]
去最大值时的方案数。根据f[i,j]
的状态转移分情况讨论有:
- 1.
f[i-1, j] > f[i-1, j-vi]
时,g[i, j] = g[i-1, j]
优化一维-->
g[j]
- 2.
f[i-1, j] < f[i-1, j-vi]
时,g[i, j] = g[i-1, j-vi]
优化一维-->
g[j-vi]
- 3.
f[i-1, j] = f[i-1, j-vi]
时,g[i, j] = g[i-1, j] + g[i-1, j-vi]
优化一维-->
g[j] + g[j-vi]
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行两个整数 v~i~,w~i~,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数,表示 方案数 模 10^9^+7 的结果。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例:
4 5
1 2
2 4
3 4
4 6
输出样例:
2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9+7;
int n,m;
int f[N], g[N];//g[i]表示体积恰好为i的方案数
int main()
{
cin >> n >> m;
//模版之--模版12.体积条件变化情况的探讨--体积刚好为i的方案数初始化
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for(int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for(int j = m; j >= v; j --)
{
int maxv = max(f[j], f[j-v] + w);
int cnt = 0;
if(maxv == f[j]) cnt += g[j];
if(maxv == f[j-v] + w) cnt += g[j-v];
g[j] = cnt % mod;
f[j] = maxv;
}
}
int res = 0;//找出最大值,即最优方案f[i]是谁
for(int i = 0; i <= m; i ++ ) res = max(res, f[i]);
int cnt = 0; //统计最大值的方案数
for(int i = 0; i <= m; i ++ )
if(res == f[i]) //统计最优解的方案
cnt = (cnt + g[i]) % mod;//所有等于最优解的体积数加起来
cout << cnt << endl;
return 0;
}
emmm其实我觉得我更习惯改写一下的版本
这个版本是直接用01背包改的,不用初始化,也不用找最大价值
int main()
{
cin >> n >> m;
g[0] = 1;//没有也是一种方案
for(int i = 0; i < n; i ++ )
{
int v, w;
cin >> v >> w;
for(int j = m; j >= v; j --)
{
int cnt = 0;
if(f[j] >= f[j-v] + w) cnt += g[j]; //方案数状态转移
if(f[j] <= f[j-v] + w) cnt += g[j-v]; //方案数状态转移
f[j] = max(f[j], f[j-v] + w); //01背包dp
g[j] = cnt % mod;
}
}
int res = f[m];
int cnt = 0; //统计最大值的方案数
for(int i = 0; i <= m; i ++ )
if(res == f[i]) //统计最优解的方案
cnt = (cnt + g[i]) % mod;//所有等于最优解的体积数加起来
cout << cnt << endl;
return 0;
}
AcWing 734. 能量石(贪心+01背包)
有一堆能量石,每个都有能量e,要吃的时间s,每秒流逝的能量l,能量最低流失为0
正在被吃的能量石能量不流失
求能获得的最多能量
这个题有很明显的局部最优特性,所以是贪心+dp,思考出贪心特性就会变成01背包问题
对于任意两个相邻能量石 i,j
- 先吃
i
再吃j
:ei' + ej' - si·lj
- 先吃
j
再吃i
:ei' + ej' - sj·li
因此只需要判断si·lj
和sj·li
的大小即可。
si·lj < sj·li
变形得si/li < sj/lj
则先吃i
再吃j
更好si·lj > sj·li
变形得si/li > sj/lj
则先吃j
再吃i
更好
因此按照si/li
的大小排序就可以形成贪心,每一步吃的都是最好的,因此就转换成了01背包问题
状态表示f[i,j]
表示所有只从前i
块能量石选,且吃的时间不超过j
的方案
属性:最大值。 状态计算01背包f[i,j]=max(f[i-1,j], f[i-1,j-s]+e-(j-s)*L)
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含整数 N,表示能量石的数量。
接下来 N 行,每行包含三个整数 S~i~,E~i~,L~i~。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y
,其中 x 是组别编号(从 1 开始),y 是可以获得的最大能量值。
数据范围
1≤T≤10 ,
1≤N≤100,
1≤Si≤100,
1≤Ei≤10^5,
0≤Li≤10^5
输入样例:
3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
输出样例:
Case #1: 105
Case #2: 8
Case #3: 500
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n;
//定义结构体存能量石,并且重定运算符实现sort贪心
struct Stone
{
int s, e, l;
bool operator< (const Stone &W) const
{
return s * W.l < l * W.s;
}
}stone[N];
int f[N];//存储转换后的01背包问题能量最大值
int main()
{
int T;
cin >> T;
for(int C = 1; C <= T; C ++ )
{
int m = 0;
cin >> n;
for(int i = 0; i < n; i ++ )
{
int s, e, l;//s是吃完要花多久,e是能量石蕴含能量,l是每秒流失多少能量
cin >> s >> e >> l;
stone[i] = {s,e,l};
m += s;//一个case里吃完所有石头要的总时间
}
//按si/li从小到大对石头排序
sort(stone, stone + n);
//模版12之--体积刚好为j的情况
memset(f, -0x3f, sizeof f);
f[0] = 0;
for(int i = 0; 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);//01背包模版,价值计算思考一下
}
//模版12之--体积刚好为j的情况--最后res max一下
int res = 0;
for(int i = 0; i <= m; i ++ ) res = max(res, f[i]);
cout << "Case #" << C << ": " << res << endl;
}
return 0;
}
-
多重背包问题
AcWing 1019. 庆功会(朴素多重背包,多重背包I)
给定金额求能购买最大价值的奖品,每种奖品数量有限
输入格式
第一行二个数n,m,其中n代表希望购买的奖品的种数,m表示拨款金额。
接下来n行,每行3个数,v、w、s,分别表示第I种奖品的价格、价值(价格与价值是不同的概念)和能购买的最大数量(买0件到s件均可)。
输出格式
一行:一个数,表示此次购买能获得的最大的价值(注意!不是价格)。
数据范围
n≤500,m≤6000 ,
v≤100,w≤1000,s≤10
输入样例:
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
输出样例:
1040
int main()
{
cin >> n >> m;
for(int i=0; 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*v<=j;k++)
f[j] = max(f[j],f[j-k*v]+k*w);
}
cout << f[m] << endl;
return 0;
}
-
完全背包问题
AcWing 1023. 买书(求方案数)
这个…求方案数的题,见一次就会了我觉得
小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。
问小明有多少种买书方案?(每种书可购买多本)
钱必须花完,没钱算一种方案
输入格式
一个整数 n,代表总共钱数。
输出格式
一个整数,代表选择方案种数。
数据范围
0≤n≤1000
输入样例:
20 输入2: 15 输入3: 0
输出样例:
2 输出2: 0 输出3: 1
//求从前i个物品选,且总体积恰好是j的最多方案
//f[j] = max(f[j],f[j-v])
int n;
int f[N];
int v[4] = {10, 20, 50, 100};
int main()
{
cin >> n;
f[0] = 1;
for(int i = 0; i < 4; i ++)
{
for( int j = v[i]; j <= n; j ++) //记得写等号
{
f[j] += f[j-v[i]];
}
}
cout << f[n];
return 0;
}
AcWing 1021. 货币系统(简化版)(完全背包方案数)
给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案
这道题完全背包体积为m,物品数为n,物品为n种面值的货币系统。
输入格式
第一行,包含两个整数n和m。
接下来n行,每行包含一个整数,表示一种货币的面值。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
n≤15,m≤3000
输入样例:
3 10
1
2
5
输出样例:
10
//注意一下这个会爆int
typedef long long LL;
const int N = 20, M = 3010;
int n, m;
LL f[M];
int main()
{
cin >> n >> m;
f[0]=1; //要初始化一下,什么都不选组成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] << endl;
return 0;
}
AcWing 532. 货币系统(NOIP 2018提高组)(这和贪心…有关系?。。)
在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。
为了方便,我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。
在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。
然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。
例如在货币系统 n=3,a=[2,5,9] 中,金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统 (m,b),满足 (m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。
他们希望你来协助完成这个艰巨的任务:找到最小的 m。
思路
要求等价最小b
数组
那么实质上就是现将a
排序,对a[i]
作为体积的背包,求a[1]~a[i-1]
的完全背包问题
f[i]
表示的就是对于a
中前i
个元素,可以用a[1]~a[i-1]
拼凑出来的方案数
输入格式
输入文件的第一行包含一个整数 T,表示数据的组数。
接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数 n。
接下来一行包含 n 个由空格隔开的正整数 a[i]。
输出格式
输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。
数据范围
1≤n≤100 ,
1≤a[i]≤25000,
1≤T≤20
输入样例:
2
4
3 19 10 6
5
11 29 13 19 17
输出样例:
2
5
//最多有100个物品,背包范围a[i]最大为25000
const int N = 110, M = 25010;
int T;
int n;
int a[N];
int f[M];
int main()
{
int T;
cin >> T;//数据的组数
while(T--)
{
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
sort(a+1, a + n+1); //这个排序要注意+1
memset(f, 0, sizeof f);
f[0] = 1;
int res = 0;
for(int i = 1; i <= n; i ++ )
{
//如果当前的a[i]不存在一种拼凑方案的话那就被选出来
if(!f[a[i]]) res ++; //f[a[i]] = 0, res ++
for(int j = a[i]; j <= a[n]; j ++ )//背包容积最大为a[m]
f[j] += f[j-a[i]];
}
cout << res << endl;
}
return 0;
}
-
分组背包问题
分组背包其实是组合数问题,很多物品很多组,有很多种互斥的选法。多重背包问题是分组背包的一种特殊形式
AcWing 1013. 机器分配(分组背包+求方案)
总公司拥有 M 台 相同 的高效设备,准备分给下属的 N 个分公司。
各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问:如何分配这M台设备才能使国家得到的盈利最大?
求出最大盈利值。
分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数 M。
这是个方案问题,只不过没有要求最小字典序输出
分组的依据为
机器个数 1 2 3
第一个公司 30 40 50
第二个公司 20 30 50
第三个公司 20 25 30
每个公司分为一组,个数对应体积,总共有三组九个物品,拿其中的物品使得体积等于总公司可分配数同时价值最大
输入格式
第一行有两个数,第一个数是分公司数 N,第二个数是设备台数 M;
接下来是一个 N×M 的矩阵,矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
输出格式
第一行输出最大盈利值;
接下 N 行,每行有 2 个数,即分公司编号和该分公司获得设备台数。
答案不唯一,输出任意合法方案即可。
数据范围
1≤N≤10 ,
1≤M≤15
输入样例:
3 3
30 40 50
20 30 50
20 25 30
输出样例:
70
1 1
2 1
3 1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 11, M = 16;
int n, m;
int f[N][M];//求方案数要开二维
int w[N][M];
int way[N]; // 用来记一下方案是什么
int main()
{
//物品数量n,体积上限m,用总公司设备数作体积上限来限制超过m的情况
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 = m; j >=0; j --)
{
f[i][j] = f[i-1][j]; //第i组物品一个都不选的情况
for(int k = 1; k <= j; k++)
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 = 1; k <= j; k++ )//这k一定是从1开始数的
{
if(f[i][j] == f[i-1][j-k]+w[i][k])
{
way[i] = k; //找到了方案 break
j-= k;
break;
}
}
}
for(int i = 1; i <= n; i ++ ) cout << i << ' ' << way[i] << endl;
return 0;
}
AcWing 487. 金明的预算方案(分组背包 + 二进制遍历 + 主附件依赖)
妈的难死屌我了
学一下#define
的用法
题意就是金明这小子有N
块钱,店里有m
个物品这小子都想买
钱不够买,所以他给每个物品分了个重要度p(1~5)
,还给这些物品分了主附件
买主件不一定买附件,买附件一定买主件,不是所有主件都有附件。
求在预算内重要级乘价格的最大值
输入格式
输入文件的第1行,为两个正整数,用一个空格隔开:N m,其中N表示总钱数,m为希望购买物品的个数。
从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数v p q,其中v表示该物品的价格,p表示该物品的重要度(1~5),q表示该物品是主件还是附件。
如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号。
思路
用PII master[N]
存主件,用vector<PII> servent[N]
存附件。存的是{v, v * p}
然后进行一个分组背包模版的写,注意这个分组背包的物品是先看主件,也就是说第一层循环把所有物品遍历一遍,看一下谁是主件,只有是主件的才有必要进行下一层循环;
第二层循环是体积从大到0;
第三层循环是二进制遍历当前组,k
从0
到1<<servent[i].size()
循环,每一个整数都代表一种组合的情况。目的是要找到[0,m]
的体积范围里所有可能性的最大值。由于主件必选,所以v, m
先初始化成主件的v
和m
。然后在[0,servent[i].size()]
的范围内循环,这一步的目的是通过k >> u & 1
来判断当前k
情况的组合中第u位附件是不是存在的,是就v += servent[i][u].v, w += servent[i][u].w
,之后判断一下,如果当前这个k
情况的物品组在j
体积内容得下那就取max
。最后f[m]
就是结果
输出格式
输出文件只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<200000)。
数据范围
N<32000,m<60,v<10000
输入样例:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出样例:
2200
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define v first
#define w second
typedef pair<int, int> PII;
const int N = 70, M = 32010;
//总钱数范围<32000, 物品个数<60,单个物品价值v<10000
//p,q 表示重要度1~5,主附件01
int v, p, q;
PII master[N]; //主件
vector<PII> servent[N]; //附件
int f[M];
int n,m;
int main()
{
cin >> m >> n; // n为物品个数,m为钱
for(int i = 1; i <= n; i ++ )
{
cin >> v >> p >> q;
//如果q为0就是主件,价格w=v*p
if(!q) master[i] = {v, v * p};
else servent[q].push_back({v, v * p}); //p为1是附件
}
for(int i = 1; i <= n; i++)
{
if(master[i].v) //如果不是master,或者v为0,都会返回false
{
for(int j = m; j >= 0; j --)
for(int k = 0; k < 1 << servent[i].size(); k++) //二进制法枚举物品组,即枚举附件
{
int v = master[i].v, w = master[i].w; //选附件时主件必须选,所以初始化为主件
for(int u = 0; u < servent[i].size(); u ++ )
if(k >> u & 1)
{
v += servent[i][u].v;
w += servent[i][u].w;
}
//如果j > 当前物品组的体积
if(j >= v) f[j] = max(f[j],f[j-v] + w);
}
}
}
cout << f[m] << endl;
return 0;
}
新年快乐!
同乐同乐!
我去 ,也太强了,, 膜拜了
一起加油呀!