背包模板
- 01背包
// 一维数组优化
for(int i=1; i<=n; i++)
{
for(int v=m; v>=c[i]; v--)
{
f[v]=max(f[v], f[v-c[i]] + w[i]);
}
}- 无限背包
for(int i = 1; i <= n; i++)
{
for(int v = c[i]; v <= m; v++)
{
f[v]=max(f[v], f[v-c[i]] + w[i]);
}
}转换成背包
如何将一个题目内容转换成一个背包问题呢?
P1734 最大约数和
题目描述
选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。
输入格式
输入一个正整数 S。
输出格式
输出最大的约数之和。
输入输出样例
- 输入 #1复制
11
- 输出 #1复制
9
说明/提示
样例说明
取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。
数据规模
S<=1000
分析
转换成背包问题:
i 这个数, 看成一个物品, 体积就是他的数值 i, 价值就是他的约数之和
背包的容积就是 s.
求装满背包时, 最大价值是多少?
每个物品只能取一次(不同的数), 所以是 01 背包, 直接套用模板吧
参考代码
#include <bits/stdc++.h>
using namespace std;
int s;
int a[1002];
int f[1002];
int sumprime()
{
for(int i = 2; i <=s; i++) {
for(int k = 2; k*k <= i; k++) {
if(i % k == 0) {
a[i] += k;
if(i/k != k)
a[i] += i/k;
}
}
a[i] += 1;
}
}
int main()
{
int i, v;
scanf("%d", &s);
sumprime();
for(i = 1; i <= s; i++)
for(v = s; v >= i; v--) {
f[v] = max(f[v], f[v-i] + a[i]);
}
printf("%d", f[s]);
return 0;
}
背包求最小值
P1679 神奇的四次方数
题目描述
在你的帮助下，v神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是dm同学，于是v神便找到了dm同学，可dm同学正在忙于研究一道有趣的数学题，为了请dm出山，v神只好请你帮忙解决这道题了。
题目描述
将一个整数m分解为n个四次方数的和的形式，要求n最小。例如，m=706,706=5^4+3^4,则n=2。
输入格式
一行，一个整数m。
输出格式
一行，一个整数n。
输入输出样例
- 输入 #1复制
706
- 输出 #1复制
2
说明/提示
数据范围：对于30%的数据，m<=5000;对于100%的数据，m<=100,000
分析
求 n 最小是多少? 而不像前面的最大值.
怎么转换成背包呢?
四方数的数值看作物品的体积, 那物品的价值就是 1, 代表能给 n 贡献 1, 也就是代表 1个 四方数. 因为每个数可以取无限多个所以是无限背包.
于是状态定义:
f[i]: 代表组成背包容积是i时, 物品的价值, 也就是组成 i 时用到的四方数个数.
状态转移(k是一个四方数):
f[i] = min(f[i], f[i- k] + 1);
初始状态:
因为是求最小值, 所以f[i]的初始状态是极大值, 同时 f[0] = 0;
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100002;
int m, n, a[21], f[N];
int main()
{
int i;
scanf("%d", &m);
for(i = 1; i <= 20; i++) {
a[i]= i * i * i * i;
if(a[i] > m)
break;
}
n = i - 1;
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for(i = 1; i <= n; i++)
for(int j = a[i]; j <= m; j++)
f[j] = min(f[j], f[j - a[i]] + 1);
printf("%d\n", f[m]);
return 0;
}
恰好背包
恰好装满：
求最大值时，除了 f[0] 为0，其他都初始化为无穷小 -0x3f3f3f3f
求最小值时，除了 f[0] 为0，其他都初始化为无穷大 0x3f3f3f3f
不必恰好装满：全初始化为 0
例题
直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是 c，价值是 w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO
输入
第一行：N 表示有多少组测试数据（N<7）。
接下来每组测试数据的第一行有两个整数M，V。M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)
输出
对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。如果不能恰好装满背包，输出NO）
样例输入
2
1 5
2 2
2 5
2 2
5 1样例输出
NO
1参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2008, V = 500008;
int t, m, v, f[V], c[N], w[N];
int main()
{
cin >> t;
while(t--)
{
cin >> m >> v;
for(int i = 1; i <= m; i++)
cin >> c[i] >> w[i];
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for(int i = 1; i <= m; i++)
for(int j = c[i]; j <= v; j++)
f[j] = max(f[j], f[j-c[i]] + w[i]);
if(f[v] > 0)
cout << f[v] << endl;
else
cout << "NO" << endl;
}
return 0;
}到达背包
P1877 [HAOI2012]音量调节
题目描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中整数 beginLevel，代表吉他刚开始的音量，整数 maxLevel，代表吉他的最大音量。音量不能小于 0 也不能大于 maxLevel。输入中还给定了 n 个整数 表示在第 i 首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入格式
第一行依次为三个整数 n，beginLevel 和 maxLevel。
第二行依次为 n 个整数 。
输出格式
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 0 或者高于 maxLevel，输出 -1。
输入输出样例
- 输入 #1复制
3 5 10
5 3 7- 输出 #1复制
10
说明/提示
分析
到达型的01背包问题
状态定义:
f[i][j]: 前 i 首歌曲能否达到音量 j
f[i][j] = 0不能达到, f[i][j] = 1 表示可以达到
音量调高表示取第 i 件物品，音量调低表示不取第 i 件物品
音量为背包容量，01背包模板题（调高调低带约束）
初始条件：f[0][beginlevel] = 1, 没演奏前可以到达beginlevel
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 55, M = 1000 + 8;
int n, st, m, a[N], f[51][1001];
int main()
{
cin >> n >> st >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
f[0][st] = 1;
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 0; j--) {
if(j - a[i] >= 0)
f[i][j] = f[i][j] || f[i-1][j-a[i]];
if(j + a[i] <= m)
f[i][j] = f[i][j] || f[i-1][j+a[i]];
}
}
for(int i = m; i >= 1; i--) {
if(f[n][i] == 1) {
cout << i;
return 0;
}
}
cout << -1;
return 0;
}
方案数
对于一个给定了背包容量、物品费用、物品间相互关系等, 给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的 max 改成 sum 即可。
例如若每件物品均是完全背包中的物品，转移方程即为
F[i, v] = sum(F[i − 1, v], F[i, v − c[i]]) 初始条件是 F[0, 0] = 1。
空间压缩后:
f[v] += f[v- c[i]];
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案
例题 P1832 A+B Problem（再升级）
题目背景
题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
1+1=? 显然是2
a+b=? 1001回看不谢
哥德巴赫猜想 似乎已呈泛滥趋势
以上纯属个人吐槽
给定一个正整数n，求将其分解成若干个素数之和的方案总数。
输入格式
一行：一个正整数n
输出格式
一行：一个整数表示方案总数
输入输出样例
- 输入 #1复制
7
- 输出 #1复制
3
说明/提示
【样例解释】
7=7
7=2+5
7=2+2+3【福利数据】
【输入】 20
【输出】 26
【数据范围及约定】
对于30%的数据 1<=n<=10
对于100%的数据，
参考代码
#include <bits/stdc++.h>
using namespace std;
int n, a[1002], prime[1002], cnt;
long long f[1002];
int GetPrime(int n)
{
for(int i = 2; i <= n; i++) {
if(a[i] == 0) {
cnt++;
prime[cnt] = i;
}
for(int j = 1; j <= cnt; j++) {
if(i * prime[j] > n)
break;
a[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
int main()
{
scanf("%d", &n);
GetPrime(n);
f[0] = 1;
for(int i = 1; i <= cnt; i++) {
for(int j = prime[i]; j <= n; j++) {
f[j] += f[j - prime[i]];
}
}
printf("%lld\n", f[n]);
return 0;
}
输出最优方案
我们现在需要考虑的是如何记录这个状态. 很明显记录每个状态的最优值,是由状态转移方程的哪一项推出来的. 如果我们知道了当前状态是由哪一个状态推出来的,那我们很容易的就能输出方案. 开数组g[i][v]记录状态f[i][v]是由状态转移方程哪一项推出.
//以01背包一维写法为例.
for(int i=1;i<=n;i++)
{
for(int j=V;j>=c[i];j--)
{
if(f[j]<f[j-c[i]]+w[i])
{
f[j]=f[j-c[i]]+w[i];
g[i][j] = true;///选第i件物品
}
else g[i][j] = false;///不选第i件物品
}
}
int t=V;
for(int i = n; i >= 1; i--)
{
if(g[i][t])
{
printf("used %d", i);
t -= c[i];//减去物品 i 的体积.
}
}最优方案的总数
这里的最优方案是指物品总价值最大的方案。以 01 背包为例。结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：F[i, v] 代表该状态的最大价值， G[i, v] 表示这个子问题的最优方案的总数，则在求 F[i, v] 的同时求 G[i, v] 的伪代码如下：
g[0][0] = 1;
for(int i = 1; i <= n; i++)
for(int v = 0; v <= V; v++) {
f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i]);
g[i][v] = 0;
if(f[i][v] == f[i-1][v]) {
g[i][v] = g[i][v] + g[i-1][v]
}
if (f[i][v] == f[i-1][v-c[i]] + w[i]) {
g[i][v] = g[i][v] + g[i-1][v-c[i]]
}
}题单
- P1734 最大约数和
- P1679 神奇的四次方数
- P1877 [HAOI2012]音量调节
- P1832 A+B Problem（再升级）
- P1510 精卫填海
- P2563 [AHOI2001]质数和分解