欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

浅谈多重背包及其优化

发布时间:2024/7/5 编程问答 4 豆豆
如意编程网 收集整理的这篇文章主要介绍了 浅谈多重背包及其优化 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

模板来源:codevs 5429

根据背包问题的相关状态转移方程,我们不难写出朴素的算法

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 inline int read() { 7 int ret=0; 8 int op=1; 9 char c=getchar(); 10 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 11 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 12 return ret*op; 13 } 14 int n,m; 15 int c[7010],v[7010],num[7010]; 16 int f[7010]; 17 int main() { 18 n=read(); m=read(); 19 for(int i=1;i<=n;i++) { 20 c[i]=read(); v[i]=read(); num[i]=read(); 21 } 22 for(int i=1;i<=n;i++) 23 for(int j=m;j>=c[i];j--) 24 for(int k=0;k<=num[i];k++) 25 if(j-c[i]*k>=0) 26 f[j]=max(f[j],f[j-c[i]*k]+v[i]*k); 27 printf("%d\n",f[m]); 28 return 0; 29 } TLE Code

在朴素算法中,我们枚举每个物品的数量作为决策,这样大大浪费时间,我们可以将物品二进制拆分来代替枚举,具体地讲,例如某种物品数量为10,那么我们将这个物品的数量拆分成1,2,4,3(相当于把这个数量为10的物品分成四个物品),然后这个问题就转化成了01背包问题。时间复杂度大大降低。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 inline int read() { 7 int ret=0; 8 int op=1; 9 char c=getchar(); 10 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 11 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 12 return ret*op; 13 } 14 int n,m,tot; 15 int f[7010],c[100010],v[100010]; 16 int main() { 17 n=read(); m=read(); 18 for(int i=1;i<=n;i++) { 19 int x=read(),y=read(),z=read(); 20 int base=1; 21 while(z>=base) { 22 c[++tot]=x*base; 23 v[tot]=y*base; 24 z-=base; 25 base<<=1; 26 } 27 if(z>0) { 28 c[++tot]=z*x; 29 v[tot]=z*y; 30 } 31 } 32 for(int i=1;i<=tot;i++) 33 for(int j=m;j>=c[i];j--) 34 f[j]=max(f[j],f[j-c[i]]+v[i]); 35 printf("%d\n",f[m]); 36 return 0; 37 } TLE Code better

 我们继续考虑优化dp,我们将状态j按照c[i]的余数分组,显然,当i为定值时,不同组的状态不能相互转移。

我们将倒序循环j的过程,改为对每个余数u∈[0,c[i]-1],倒序循环p,这样状态j=u+p*c[i]。

 于是我们得到了新的状态转移方程:

 类比Fence一题,我们便可以使用单调队列进行优化,这种算法的时间复杂度与普通的背包相等,可以通过本题。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 int n,m,c[7010],v[7010],num[7010],f[7010]; 8 int q[7010]; 9 inline int read() { 10 int ret=0; 11 int op=1; 12 char c=getchar(); 13 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 14 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 15 return ret*op; 16 } 17 inline int calc(int i,int u,int k) { 18 return f[u+k*c[i]]-k*v[i]; 19 } 20 int main() { 21 n=read(); m=read(); 22 memset(f,0xcf,sizeof(f)); 23 f[0]=0; 24 for(int i=1;i<=n;i++) { 25 c[i]=read(); v[i]=read(); num[i]=read(); 26 for(int u=0;u<c[i];u++) { 27 int l=1,r=0; 28 int maxx=(m-u)/c[i]; 29 for(int k=maxx-1;k>=max(0,maxx-num[i]);k--) { 30 while(l<=r&&calc(i,u,q[r])<=calc(i,u,k)) r--; 31 q[++r]=k; 32 } 33 for(int p=maxx;p>=0;p--) { 34 while(l<=r&&q[l]>p-1) l++; 35 if(l<=r) f[u+p*c[i]]=max(f[u+p*c[i]],calc(i,u,q[l])+p*v[i]); 36 if(p-num[i]-1>=0) { 37 while(l<=r&&calc(i,u,q[r])<=calc(i,u,p-num[i]-1)) r--; 38 q[++r]=p-num[i]-1; 39 } 40 } 41 } 42 } 43 int ans=0; 44 for(int i=1;i<=m;i++) 45 ans=max(ans,f[i]); 46 printf("%d\n",ans); 47 return 0; 48 } AC Code

 

转载于:https://www.cnblogs.com/shl-blog/p/10990625.html

总结

以上是如意编程网为你收集整理的浅谈多重背包及其优化的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。