蓝桥杯备赛 背包问题
背包问题
![[背包问题.png]]
01背包
1.题意概要：有
n
n
n个物品和一个容量为
V
V
V的背包，每个物品有重量
w
i
w_i
wi和价值
v
i
v_i
vi 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
要求:每个物品只能拿一次,所以每个物品只有拿或不拿两种状态，故称01背包
2.状态:dp[i][j]表示到第i个物品为止(不一定拿)，到容量j为止，背包的最大价值
状态转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)(注意先判断j>=w)(不关心有没有拿，只关心最大价值)
最终状态:dp[n][V]
小明的背包1
学习:
(1)模版题，可以不用开w[i],v[i]数组记录，反正是一个一个物品枚举的
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+10,V=1e3+10;
int n,vol,dp[N][V];
int main(){
ios::sync_with_stdio(false);
cin>>n>>vol;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=1;j<=vol;j++){
//判断是否越界，即能不能放下第i个物品
if(j>=w) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][vol];
return 0;
}
01背包一维滚动数组优化
学习:
(1)二维数组的第一维度dp[i]和dp[i-1]本质就是第i-1层的值来转移给第i层，就是用遍历i来实现的，因此可以优化为滚动一维数组，让前面的旧值转移给后面的新值，所以一个维度dp[j]就够了，表示背包容量到j为止的最大价值,状态转移方程:
dp[j]=max(dp[j],dp[j-w]+v)
(2)背包容量倒序遍历，从
V
V
V开始
w
i
w_i
wi,原因如下图:
![[01背包优化图.png]]
黄色块为旧值，绿色块为新值，左侧二维dp[i]的绿色新值都是由dp[i-1]黄色旧值转移而来，所以背包容量从前往后或从后往前无所谓，而右侧一维只能是黄色旧值转移给绿色新值，所以从后往前遍历，遇到个新值dp[j],从前面的旧值dp[j-w]转移过来，如果从前往后遍历，会出现dp[j-w2]由dp[j-w2-w1]转移过一次，变成新值(不再是旧值dp[j-w2])，dp[j]由新值dp[j-w2]转移过来，相当于加上了两次物品，例如:
w v
物品
1 1 2
j 0 1 2
dp[j](从前往后) 0 2 4(出现问题，考虑了两次物品1)
dp[j](从后往前) 0 2 2
小明的背包1优化代码
#include <bits/stdc++.h>
using namespace std;
const int V=1e3+10;
int n,vol,dp[V];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>vol;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=vol;j>=w;j--){ //倒序遍历
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[vol];
return 0;
}
背包与魔法
学习:
(1)这题是01背包的变体，因为多了一个是否使用魔法，且最多使用一次，就相当于状态dp多了一个维度的变量(这个思想很重要),就有两大种状态dp[j][0],dp[j][1],三种状态转移:1.不加入物品2.加入物品不使用魔法3.加入物品使用魔法，以及相应的状态转移方程
//不使用魔法,一般的一维01背包
dp[j][0]=max(dp[j][0],dp[j-w][0]+v);
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);
//使用魔法
if(j>=(w+k)) dp[j][1]=max(dp[j][1],dp[j-(w+k)][0]+2*v);//精华所在
(2)状态转移方程在同一个反向遍历j下转移，表示对当前物品的转移，因为j最小到w，所以第二种状态转移方程要有个判断j>=(w+k)
(3)求多个元素的最大值，中间套个列表({})即可
maxn=max({1,2,3,4})
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+10,M=1e4+10;
int n,m,k;
ll dp[M][2]; //第一维度为背包重量j，第二维度表示是否使用魔法
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=m;j>=w;j--){
//不使用魔法,一般的一维01背包
dp[j][0]=max(dp[j][0],dp[j-w][0]+v);
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);
//使用魔法
if(j>=(w+k)) dp[j][1]=max(dp[j][1],dp[j-(w+k)][0]+2*v);
}
}
cout<<max(dp[m][0],dp[m][1]);
return 0;
}
完全背包
(1)特征:每个物品有无限多个，可以被拿无限多次
(2)状态dp[j]表示到体积j为止的最大价值状态转移方程:
dp[j]=max(dp[j],dp[j-w]+v)跟一维01背包类似，但是不同点在于完全背包要从前往后遍历，这样每个物品能被拿无限多次，用新数据来更新新数据，而一维01背包要从后往前遍历，确保每个物品只拿一次，用旧数据来更新新数据
小明的背包2
学习:
(1)模版题
代码:
#include <bits/stdc++.h>
using namespace std;
const int V=1e3+10;
int n,vol,dp[V];
int main(){
ios::sync_with_stdio(false);
cin>>n>>vol;
for(int i=1;i<=n;i++){
int w,v;
cin>>w>>v;
for(int j=w;j<=vol;j++){ //正序遍历
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[vol];
return 0;
}
多重背包
(1)特征:第i个物品有
s
i
s_i
si个，共有s+1种状态(取0,1,2…s个)
(2)核心解决办法:将
s
i
s_i
si个第i个物品当成独立的s个物品(遍历s次即可)，每个
s
i
j
s_ij
sij物品就只有一个，就是01背包问题了
小明的背包3
学习:
(1)多重背包模版题
代码:
#include <bits/stdc++.h>
using namespace std;
const int V=2e2+10;
int n,vol,dp[V];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>vol;
for(int i=1;i<=n;i++){
int w,v,s;
cin>>w>>v>>s;
//遍历s次，相当于把第i个物品拆成s个i_s物品，每个i_s物品只有一个，为01背包问题
for(int k=1;k<=s;k++){
//01背包倒序遍历
for(int j=vol;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
}
cout<<dp[vol];
return 0;
}
二进制优化多重背包
(1)将s个物品拆分成s组，每组一个的经典多重背包时间复杂度为O(n*s*V),s过大会超时
(2)因为任意一个数都有其对应的二进制数，令s=1+2+4+8+…+其他，一个物品可以分为约log2(s)组,就可以将几个二进制数组合表示0-s这s+1种中的任意状态，例如:
s=14=1+2+4+7(其他)，要取10个物品，就相当于依次取1,2,7个物品即可,
所以可以将物品数量拆分为多个二进制组合，减少状态转移次数
(3)修改s的遍历即可，不再是1个1个加，而是倍数乘,而2个物品对应修改为2w,2v即可,最终的复杂度为O(n*log2(s)*V)
新一的宝藏搜寻加强版
学习:
(1)
s
i
s_i
si最大能到2e4，普通多重背包会超时，需要二进制优化,记得最后一个剩余的数要单独遍历一次
代码:
#include <bits/stdc++.h>
using namespace std;
const int V=2e4+10;
int n,vol,dp[V];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>vol;
for(int i=1;i<=n;i++){
int w,v,s;
cin>>w>>v>>s;
int t=0;//t为二进制数累加和
for(int k=1;(k+t)<=s;k*=2){
t+=k;
//01背包倒序
for(int j=vol;j>=k*w;j--){
dp[j]=max(dp[j],dp[j-k*w]+k*v);
}
}
//最后剩余部分为s-t
for(int j=vol;j>=(s-t)*w;j--){
dp[j]=max(dp[j],dp[j-(s-t)*w]+(s-t)*v);
}
}
cout<<dp[vol];
return 0;
}
二维费用背包
(1)特征:物品除了价值v,体积w两个特征外，还多了一个重量m特征，现在有两个限制条件:体积不超过W和重量不超过M的最大价值
(2)解决方法:一维01背包变成二维即可，仍然倒序更新，dp[i][j]表示体积到i为止，重量到j为止的最大价值,状态转移方程:dp[i][j]=max(dp[i][j],dp[i-w][j-m]+v)
小蓝的神秘行囊
学习:
(1)二维费用背包模版题
代码:
#include <bits/stdc++.h>
using namespace std;
const int V=105,M=105;
int n,vol,mm,dp[V][M];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>vol>>mm;
for(int i=1;i<=n;i++){
int v,m,w;
cin>>v>>m>>w;
//二维倒序遍历
for(int j=vol;j>=v;j--){
for(int k=mm;k>=m;k--){
dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);
}
}
}
cout<<dp[vol][mm];
return 0;
}
分组背包
(1)特征:共有n组物品，每组物品里面有s个物品，每个物品有对应的w和v，每组物品最多只能取一个(区别所在),所有状态转移的第一维度是组，且没用一维优化，因为每一组的w和v有多个，不是固定的
(2)解决问题:dp[i][j]表示到第i组为止，体积j为止的最大价值,状态转移方程(好好理解)
dp[i][j]=dp[i-1][j] //初始化这一组都不取，就是上一组的状态(01背包是通过一个状态转移方程全做了)
dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v) //注意第一个是dp[i][j]，而不是dp[i-1][j],因为每一组最多取一个物品，相当于比较取第i组取之前某个物品的最大价值(dp[i][j])和第i组取当前这个物品的最大价值(dp[i-1][j-w]+v)相比较
(3)正序倒序无所谓，因为两个维度了
小明的背包5
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=105,V=105;
int n,vol,dp[N][V];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>vol;
//遍历每一组
for(int i=1;i<=n;i++){
int s;
cin>>s;
//这一组商品都不拿,等价于初始化dp[i][j]
for(int j=0;j<=vol;j++) dp[i][j]=dp[i-1][j];
//遍历每一组的每一个物品,考虑拿不拿
while(s--){
int w,v;
cin>>w>>v;
//从上一组转移过来，而不是从上一个物品转移过来
for(int j=w;j<=vol;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v); //第一个是dp[i][j],保证每一组最多取一个物品
}
}
}
cout<<dp[n][vol];
return 0;
}
蓝桥杯真题
砝码称重
学习:
(1)不是典型的背包问题，但是将动态规划的思想运用的淋漓尽致
首先定义一个状态:dp[i][j]表示到第i个砝码为止，到重量j为止，是否可以称出重量j，为0/1,
再考虑i和j的边界，i最多到n，而j最多到sum，不是到V
再考虑它由哪几种状态转移而来:
1.不拿砝码，由dp[i-1][j]转移而来
2.拿砝码放左侧，由dp[i-1][abs(j-w)](放左侧相当于加上w，由于镜像,abs(j-w)->j)
3.拿砝码放右侧,由dp[i-1][j+w]转移而来(放右侧相当于减去w，j+w->j)
![[砝码称重.png]]
代码:
(1)法一:好理解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,V=1e5+10;
int n,w[N],dp[N][V];//dp[i][j]表示到第i个砝码为止，到重量j为止，是否可以称出来，为0/1
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=sum;j++){ //最大重量到sum
//1.好理解的
//先从前i-1个砝码状态转移过来
dp[i][j]=dp[i-1][j];
//如果上一个状态称不出来重量j，看看有了第i个砝码能不能称出重量j
if(dp[i][j]==0){
//当前砝码就是重量j
if(w[i]==j) dp[i][j]=1;
//重量j+w[i]能称出来，当前砝码放另一侧，减去w[i],j+w[i]->j
if(dp[i-1][j+w[i]]) dp[i][j]=1;
//重量abs(j-w[i])能称出来，当前砝码放同侧,加上w,abs(j-w[i])->j
//取abs是因为不确定对于自己这一侧来看重量是正是负(自己这一侧为正值)
if(dp[i-1][abs(j-w[i])]) dp[i][j]=1;
}
}
}
ll ans=0;
for(int j=1;j<=sum;j++){
if(dp[n][j]==1) ans++;
}
cout<<ans;
return 0;
}
(2)法二:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,V=1e5+10;
int n,w[N],dp[N][V];//dp[i][j]表示到第i个砝码为止，到重量j为止，是否可以称出来，为0/1
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
dp[0][0]=1; //保证当前砝码就是重量j的情况
for(int i=1;i<=n;i++){
for(int j=0;j<=sum;j++){ //从0开始,最大重量到sum
//2.三种状态转移而来,且dp[i][j]值为0或1，用或操作
dp[i][j]=dp[i-1][j]||dp[i-1][j+w[i]]||dp[i-1][abs(j-w[i])];
}
}
ll ans=0;
for(int j=1;j<=sum;j++){ //从1开始
if(dp[n][j]==1) ans++;
}
cout<<ans;
return 0;
}