无废话版前言(对于这篇分享,神犇们可以【点个栈】走啦~
仅希望本分享对所有OIer的算法之旅有些许帮助
-----(玖^一些专用学习录)
背包类型:
1.01背包问题
2.完全背包问题
3.多重背包问题
4.分组背包问题
5.二维背包
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
分析
对于本题我们不妨记
$$f[i][j]$$
表示只看前$i$个物品,总体积是$j$的情况下,总价值最大是多少?
首先根据题目分析可以知道,每件物品只有不选或者选两种情况,记为$0$和$1$:
$$①f[i][j]=f[i−1][j]$$
$$②f[i][j]=f[i−1][j−v[i]]+w[i]$$
其中第一个式子为不选第$i$个物品,第二个式子为选第$i$个物品。
对每一种情况都进行一次记录其最大值,即
$$f[i][j]=max(①,②)$$
根据以上分析可知
$$result=max(f[n],[0∼V])$$
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
int v[N],w[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=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]);
}
int res=0;
for(int i=0;i<=m;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}
当然这个题不必把每一层的值都记下来,因此本题使用一维数组来对上面的方法进行优化。
虽说我们并没有将每一层的值都记录下来,但是我们再每一次循环的时候都会将每一行的值进行更新替换。
对此,如果我们还想使用上一行的值的话,只能通过从后往前进行更新了。
so:
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int v[N],w[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.完全背包问题
问题描述
有 $N$种物品和一个容量是 $V$ 的背包,每种物品都有无限件可用。
第 $i$ 种物品的体积是 $vi$,价值是 $wi$。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,$N$,$V$,用空格隔开,分别表示物品种数和背包容积。
接下来有 $N$ 行,每行两个整数 $vi$,4wi$,用空格隔开,分别表示第 $i$ 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
$0<N,V≤1000$
$0<vi,wi≤1000$
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
分析
同01背包,我们不妨记$[i]$表示为总体积是$i$的情况下,最大价值是多少。
其结果为
$$result=max(f[0…m])$$
实际上在01背包中的第二个代码中,我们仅需把第二个循环中的内层循环顺序做修改即可,即:
for(int j=v[i];j<=m;j++)
关于循环反过来正确的证明如下:
1.对于第一个物品考虑来说自然有
$$f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10$$
显然是正确的
2.假设考虑前$i-1$个物品之后,所有的$f[j]$都是正确的。
3.来证明:在前$i$个物品中,所有的$f[j]$也都是正确的,
不妨固定某一个$j$,如果最优解包含了$k个v[i]$,则一定会在循环内有
$$f[j−k⋅v[i]]=max(f[j−k⋅v[i]],f[j−k⋅v[i]−v[i]]+w[i])$$
且一定会枚举到
$$f[j−k∗v[i]]$$
其中
$$f[j−k∗v[i]]$$
为前$i-1$个物品的值
$$f[j−k∗v[i]−v[i]]$$
为前$i$个物品的值
无论如何,最后都会传递到
$$max(f[v[i]],f[0]+w[i])$$
由2可知
$$f[j]都是正确的⇒f[v[i]]也一定都是正确$$
又:
$$f[0]=0$$
那么
$$w[i]一定正确⇒max(f[v[i],f[0]+w[i]])一定正确⇒f[j−k∗v[i]]一定正确⇒f[j]一定正确$$
以上,得证
代码:
#include<bits/stdc++.h>
using namespace std;
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;
cin>>v>>w;
for(int j=v;j<=m;j++)
f[j]=max(f[j],f[j-v]+w);
}
cout<<f[m]<<endl;
return 0;
}
3.多重背包问题(easy)
问题描述
有 $n$ 种物品要放到一个袋子里,袋子的总容量为 $m$,第 $i$ 种物品的体积为 $vi$,把它放进袋子里会获得 $wi$ 的收益,一共有 $li$ 个。问如何选择物品,使得在物品的总体积不超过 $m$ 的情况下,获得最大的收益?请求出最大收益。
数据范围
$$1≤n,m,vi,wi,li≤100$$
分析
第 $i$ 种物品可以使用 $li$ 次, 我们可以把它拆成 $Ii$个物品,每个物品只可以用一次。即转换成01背包问题。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int v[N],w[N],l[N];
int main(){
cin >> n >> m;
for(int i = 1;i <= n; i++) cin >> v[i] >> w[i] >> l[i];
for(int i = 1; i <= n; i++)
for(int k = 1;k <= l[i];k++)
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;
}
4.多重背包问题(medium)
与easy版本不同的是:该题的数据范围更大了。
问题描述
有 $n$种物品要放到一个袋子里,袋子的总容量为 $m$,第 $i$ 种物品的体积为 $vi$,把它放进袋子里会获得 $wi$ 的收益,一共有 $li$ 个。问如何选择物品,使得在物品的总体积不超过 $m$ 的情况下,获得最大的收益?请求出最大收益。
数据范围
$$1≤n,m,vi,wi,li≤2000$$
分析
通过二进制拆分的方法可以优化本题。
令 $m$ 为最大的 $i$ 满足
$$2i+1−1≤n$$
, 我们从
$$1,2,4,8,16,⋯,2^m,n−2^m+^1+1$$
中选一些数字相加,就可以得出任意$[0,n]$ 内的值,每个数字只能用一次。
引理:从
$$1,2,⋯,2^m$$
中选一些数字相加,可以得出任意
$$[0,2^m+^1)$$
内的值,每个数字只能用一次。
用数学归纳法进行证明:
当 m = 0 的时候显然是成立的;
假设当 m = k 时也成立,也就是从
$$1,2,⋯,2^k$$
中选一些数字相加,可以得出任意
$$[0,2^k+^1)$$
内的值;
不难知道 对
$$[0,2^k+^2)$$
内的值可以从
$$1,2,⋯,2^k$$
中选一些数字相加得到;
也就是说对任意 m = k + 1 也成立。
同样:对于在
$$[2^m+^1,n]$$
内的值,我们取
$$n−2^m+^1+1$$
后,剩下的数字在
$$[2^m+^2−n−1,2^m+^1)$$
内,也可以从
$$1,2,⋯,2^m$$
中选一些数字相加得到。
而通过以上的操作,我们可以把它拆成 $O(log n)$ 个物品,每个物品只能用一次。
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, f[2001], v[2001], w[2001], l[2001];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> l[i];
}
for(int i = 1; i <= n; i++) {
int res = l[i];
for(int k = 1; k <= res; res -= k, k *= 2)
for(int j = m; j >= v[i] * k; j--)
f[j] = max(f[j],f[j - v[i] * k] + w[i] * k);
for(int j = m; j >= v[i] * res; j--)
f[j] = max(f[j], f[j - v[i] * res] + w[i] * res);
}
cout << f[m] << endl;
}
5.多重背包问题(hard)
与easy和medium版本不同的是:该题的数据范围更大了。
问题描述
有 $n$ 种物品要放到一个袋子里,袋子的总容量为$m$,第$i$ 种物品的体积为 $vi$,把它放进袋子里会获得$ wi$ 的收益,一共有 $li$ 个。问如何选择物品,使得在物品的总体积不超过$m$的情况下,获得最大的收益?请求出最大收益。
数据范围
$$1≤n,m,vi,wi,li≤10000$$
分析
把考虑了前 $i$ 组物品以后,总体积为 $0~m$ 时的最大收益都记下来。
考虑了前 $i$ 组物品, 总体积为 $j$ 时分成两种情况:
Case 1: 第 $i$ 组物品一个没取,问题就变成了考虑前 $i - 1$ 组物品,总体积为 $j$ 时的情况。
Case 2: 第 $i$ 组物品取了, 我们枚举取了其中的物品$ k$ , 问题变成了考虑了前$ i - 1$ 组物品, 总体积为 $j - v_i * k$ 时的情况。
$f[i] [j]$ 表示考虑了前 $i$ 组物品,总体积为 $j $时的最大收益。
需对时间复杂度进行优化
在某一类下标 $k$ 的位置,可以转移到下表在 $[k + 1,k + l_i]$ 中的位置。
那么将 $f[k] - k * w_i$放进单调队列即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, v, w, t, f[10001], c[10001][2];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v >> w >> t;
for(int j = 0; j < v; j++) {
int k = 0, l = 1;
for(int p = j, x = 1; p <= m; p += v, ++x){
int e = f[p] - x * w, r = x + t;
for(; k >= l && c[k][0] <= e; --k);
c[++k][0] = e; c[k][1] = r;
f[p] = c[l][0] + x * w;
for(; k >= l && c[l][1] == x; ++l);
}
}
}
cout << f[m] << endl;
}
6.分组背包
问题描述
有 $n$ 种物品要放到一个袋子里,袋子的总容量为 $m$。第 $i$ 个物品属于第 $ai$ 组,每组物品我们只能从中选择一个。第 $i$ 种物品的体积为 $vi$,把它放进袋子里会获得 $wi$ 的收益。问如何选择物品,使得在物品的总体积不超过 $m$ 的情况下,获得最大的收益?请求出最大收益。
数据范围:
$$1≤n,m,ai,vi,wi≤1000$$
分析
把考虑了前 $i$ 组物品以后,总体积为 $0~m$ 时的最大收益都记下来。
考虑了前 $i$ 组物品, 总体积为 $j$ 时分成两种情况:
Case 1: 第 $i$ 组物品一个没取,问题就变成了考虑前 $i - 1$ 组物品,总体积为 $j$ 时的情况。
Case 2: 第 $i$ 组物品取了, 我们枚举取了其中的物品 $k$ , 问题变成了考虑了前$ i - 1 $组物品, 总体积为 $j - v_k $时的情况。
$f[i] [j]$ 表示考虑了前 $i $组物品,总体积为 $j$ 时的最大收益。
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, a[1001], v[1001], w[1001], f[1001][1001];
vector<int> c[1001];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> v[i] >> w[i];
c[a[i]].push_back(i);
}
for(int i = 1; i <= 1000; i++) {
for(int j = 0; j <= m ; j++) {
f[i][j] = f[i - 1][j];
for(auto k : c[i]) {
if(v[k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[k] ] + w[k]);
}
}
}
cout << f[1000][m] << endl;
}
优化代码
#include<bits/stdc++.h>
using namespace std;
int n, m, a[1001], v[1001], w[1001], f[1001];
vector<int> c[1001];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> v[i] >> w[i];
c[a[i]].push_back(i);
}
for(int i = 1; i <= 1000; i++)
for(int j = m; j ; j--)
for(auto k : c[i])
if(v[k] <= j)
f[j] = max(f[j], f[j - v[k]] + w[k]);
cout << f[m] << endl;
}
7.二维背包
题目描述
有 $n$ 种物品要放到一个袋子里,袋子的总容量为 $m$,我们一共有 $k$ 点体力值。第
$i$种物品的体积为 $vi$,把它放进袋子里会获得 $wi$ 的收益,并且消耗我们 $ti$ 点体力值,每种物品只能取一次。问如何选择物品,使得在物品的总体积不超过 $m$ 并且花费总体力不超过$ k$ 的情况下,获得最大的收益?请求出最大收益。
数据范围:
$$ 1≤n,m,k,ai,vi,wi≤100 $$
分析
相较于分组背包就是多了一个体力限制。
把考虑了前 $i$ 组物品以后,总体积为 $0~m$ ,总体力为 $0~k$ 时的最大收益都记下来。
考虑了前 $i$ 组物品, 总体积为 $j$,总体力为 $x$ 时分为两种情况:
Case 1: 第$ i$ 组物品一个没取,问题就变成了考虑前 $i - 1$ 组物品,总体积为$ j$ 时,总体力为$ x$ 时的情况。
Case 2: 第$ i$ 组物品取了, 我们枚举取了其中的物品$ k$ , 问题变成了考虑了前 $i - 1$ 组物品, 总体积为 $j - v_k$,总体力为$ x - t_i $时的情况。
$f[i] [j] [x]$ 表示考虑了前$ i$ 组物品,总体积为 $j$ ,总体力为$ x$ 时的最大收益。
代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, k, v[1001], w[1001], t[1001], f[101][101][101];
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> t[i];
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m ; j++)
for(int x = 0; x <= k; x++) {
f[i][j][x] = f[i - 1][j][x];
if(j >= v[i] && x >= t[i])
f[i][j][x] = max(f[i][j][x], f[i - 1][j - v[i]][x - t[i]] + w[i]);
}
cout << f[n][m][k] << endl;
}
优化代码:
#include<bits/stdc++.h>
using namespace std;
int n, m, k, v[1001], w[1001], t[1001], f[101][101];
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> t[i];
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i] ; j--)
for(int x = k; x >= t[i]; x--)
f[j][x] = max(f[j][x], f[j - v[i]][x - t[i]] + w[i]);
cout << f[m][k] << endl;
}
建议将 $max$
$max$
改为 $\max$$\max$
啊哈,做的有些匆忙,抱歉啊hh
佬的单调队列好整洁%%%
啊哈,(还是菜的一批捏