背包问题集合
创始人
2024-06-01 19:35:24
0

文章目录

  • 01背包
  • 多重背包
    • 二进制优化多重背包
    • 单调队列优化
  • 完全背包
  • 混合背包
  • 有依赖的01背包

鉴于 @浮生闲 问了我单调队列优化多重背包的问题,我在以前整理的基础上加了对单调队列优化多重背包较为详细的解释后更新了一版。

01背包

给定n种物品(每种仅一个)和一个容量为c的背包,要求选择物品装入背包,使得装入背包中物品的总价值最大。

#include
using namespace std;
int dp[405][1505];
int w[405],v[405];int main()
{int n,c,i,j;while(~scanf("%d%d",&n,&c)){for(i=0;i<405;i++)for(j=0;j<1505;j++)dp[i][j]=0;for(i=1;i<=n;i++)scanf("%d",&w[i]);for(i=1;i<=n;i++)scanf("%d",&v[i]);int bag=c;int ma=0;for(i=1;i<=n;i++){for(j=1;j<=bag;j++){if(jdp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);ma=max(ma,dp[i][j]);}//cout<  using namespace std;  
int w[105],v[105];  
int dp[2][1005];//滚动数组优化01背包  
//滚动数组优化01背包   
int main()  
{  int t,m,res;  scanf("%d%d",&t,&m);  //读入数据  for(int i=1;i<=m;i++)  scanf("%d%d",&w[i],&v[i]);  for(int i=1;i<=m;i++)  {  for(int j=t;j>=0;j--)  {  if(j>=w[i])  dp[i%2][j]=max(dp[(i-1)%2][j-w[i]]+v[i],dp[(i-1)%2][j]);  else dp[i%2][j]=dp[(i-1)%2][j];  }  }  }  //输出最后一个数据  printf("%d",dp[m%2][t]);  
}  //一维优化01背包  
#include   using namespace std;  
int w[105],v[105];  
int dp[1000];  
int main()  
{  int t,m,res;  scanf("%d%d",&t,&m);  for(int i=1; i<=m; i++)  scanf("%d%d",&w[i],&v[i]);  for(int i=1; i<=m; i++)  for(int j=t; j>=w[i]; j--)  dp[j]=max(dp[j-w[i]]+v[i],dp[j]);  printf("%d",dp[t]);  return 0;  
}  

多重背包

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

二进制优化多重背包

通过将物品合并转化成01背包的形式
时间复杂度:O(V∗Σlogn[i])O(V*Σlog n[i])O(V∗Σlogn[i])

#include   
using namespace std;  int n,m;//n个种类,m代表包总体积  
int v[11010],w[11010];//v代表体积,w代表价值  
int dp[2010];  
int main()  
{  scanf("%d%d",&n,&m);  int cnt=0;//cnt统计新的种类  for(int i=1; i<=n; i++)  {  int a,b,s;//体积,价值,数量  scanf("%d%d%d",&a,&b,&s);  //将s件用二进制转换为log2s堆  for(int k=1; k<=s; k<<=1)  {  v[++cnt]=k*a;//前++,第1种,第二种.....  w[cnt]=k*b;  s-=k;  }  if(s)//s有剩余,自立为新品种  {  v[++cnt]=s*a;  w[cnt]=s*b;  }  }  for(int i=1; i<=cnt; i++)  for(int j=m; j>=v[i]; j--)  dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//动态转移方程和01背包完全相同  printf("%d",dp[m]);  return 0;  
}  

单调队列优化

以本题为例:6. 多重背包问题 III

尝试理解前建议先学习单调队列和完全背包。
单调队列入门
这种做法当作完全背包来理解,多重背包因为有数量限制,向前遍历的个数k是受到数量s限制的,而这个数量限制就可以理解成滑动窗口的宽度。通过单调队列来优化。每次内层循环队头弹出超过滑动窗口宽度的元素,队尾弹出不优的元素(在后面的转移过程中不可能用到它们来更新)。

先从朴素的写法入手:

for(int i=0;iint v,w,s;//体积 价值 数量cin>>v>>w>>s;for(int j=m;j>=0;j--)for(int k=1;k<=s&&k*v<=j;k++)f[j]=max(f[j],f[j-k*v]+k*w;
}

队列的单调性就是基于f[i][j] = max(f[i-1][j],f[i-1][j-v] + w,...,f[i-1][j-k*v]+k*w,要将前i - 1个物品的方案基础上不停尝试放入第i个物品,遍历取最大值。f[i-1][j-k*v]+k*w表示,总空间是j,有且仅有k个物品i,其余空间通过前i - 1个物品填充的最大价值。

还有一个细节需要注意:
比如我刚刚更新的f[7],然后去更新f[9],就需要f[7],f[5],f[3],但是f[7],f[5],f[3]都已经更新过了,就不能再用了。于是添加一个数组g存放f数组的初始值,也就是还没有更新的f数组的值,然后将g数组用单调队列维护,每次更新f中的值只需要从g中所对应的窗口选出最大的即可。

#include
using namespace std;
const int N=20010;
int f[N],g[N],q[N],n,m,v,w,s;
//f 用于状态转移,g 拷贝,q 记录入队元素的“位置”
int main()
{cin>>n>>m;for(int i=0;icin>>v>>w>>s;//单种物品的:体积 价值 数量memcpy(g,f,sizeof(f));for(int j=0;jint hh=0,tt=-1;for(int k=j;k<=m;k+=v)//枚举一个同余类中的元素{if(hh<=tt&&q[hh]

时间复杂度:O(NM)O(NM)O(NM)

完全背包

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是v[i],价值是val[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

#include   
using namespace std;  int N,V;  
int v[1010],val[1010];  
int dp[1010][1010];  
int main()  
{  scanf("%d%d",&N,&V);  for(int i=1; i<=N; i++)  {  scanf("%d%d",&v[i],&val[i]);  }  for(int i=1; i<=N; i++)  for(int j=0; j<=V; j++)  {  dp[i][j]=dp[i-1][j];//继承上一个背包  if(j>=v[i])  dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]);  }  printf("%d",dp[N][V]);  return 0;  
} 

一维优化

#include   
using namespace std;    
int N,V;  
int v[1010],val[1010];  
int dp[1010];  
int main()  
{  scanf("%d%d",&N,&V);  for(int i=1; i<=N; i++)  {  scanf("%d%d",&v[i],&val[i]);  }  for(int i=1; i<=N; i++)  for(int j=0; j<=V; j++)  {  dp[j]=dp[j];//此时右边的dp[j]是上一层i-1的dp[j],然后赋值给了当前i的dp[i]  if(j>=v[i])  dp[j]=max(dp[j],dp[j-v[i]]+val[i]);//dp[j-v[i]],已经被算过             }  printf("%d",dp[V]);//输出最大体积,即最优解  return 0;  
}  

混合背包

//混合背包,k==1表示只取一件(01背包),k>1多重背包,k==-1完全背包   
#include  
using namespace std;  
int dp[20005],w,v,k,s,n;  
int main()  
{  cin>>n>>s;  while(n--)  {  cin>>w>>v>>k;  if(k>=1)//多重背包与01背包   {  int x=1;  while(k>x)  {  for(int j=s;j>=x*w;j--)  f[j]=max(f[j-w*x]+v*x,f[j]);  k-=x;  x<<=1;  }  for(int j=s;j>=w*k;j--)   f[j]=max(f[j-w*k]+v*k,f[j]);  }  else //完全背包   for(int j=w;j<=s;j++)  f[j]=max(f[j-w]+v,f[j]);  }  cout<

有依赖的01背包

P1064 [NOIP2006 提高组] 金明的预算方案

#include 
using namespace std;int num,sum;
int bag[32500];
int v[65][3];
int w[65][3];int main()
{cin>>sum>>num;for(int i=1;i<=num;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);if(!z) v[i][0]=x*y,w[i][0]=x;else if(!v[z][1]) v[z][1]=x*y,w[z][1]=x;else v[z][2]=x*y,w[z][2]=x;}for(int i=1;i<=num;i++){for(int j=sum;j>=w[i][0];j--){bag[j]=max(bag[j],bag[j-w[i][0]]+v[i][0]);if(j>=w[i][0]+w[i][1]) bag[j]=max(bag[j],bag[j-w[i][0]-w[i][1]]+v[i][0]+v[i][1]);if(j>=w[i][0]+w[i][2]) bag[j]=max(bag[j],bag[j-w[i][0]-w[i][2]]+v[i][0]+v[i][2]);if(j>=w[i][0]+w[i][1]+w[i][2]) bag[j]=max(bag[j],bag[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);}}cout<

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...