好贷网好贷款

动态规划 多重背包 优化 poj 1276

发布时间:2016-12-4 16:15:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"动态规划 多重背包 优化 poj 1276",主要涉及到动态规划 多重背包 优化 poj 1276方面的内容,对于动态规划 多重背包 优化 poj 1276感兴趣的同学可以参考一下。

题意: 这道题的意思是给你一堆钱,各种面值的都有,比如10块的5张,5块的3张,2块的1张,请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额,比如cash=33块。我们可以取3张10块+2张1块=32,就是我们可以找到的那个最接近且小于33的数额。 思路: dp[i]用来表示第i大小金额的值是否能够取到。 参考:http://cavenkaka.iteye.com/blog/1541359 自己写的多重背包基本算法:(结果TLE) #include <iostream> #include <stdio.h> #include <cstring> using namespace std; //多重背包为题 //动态方程 //F[i][v] = max{ F[i-1][V-vi*k] + k*ci} //放入k个v k从0到ni ni为i物品的个数 F[i][v] // //F[i][v] 为第i个物品存入容量为V的背包能取得的最大值 // // //初始值 //F[ int V,n; #define MAX_V (100000 +1) #define MAX_N (10+1) int F[MAX_N][MAX_V]; int NV[MAX_N]; int CV[MAX_N]; int main() { while(cin >> V >> n) { for(int i=1;i<=n;i++) cin>>NV[i]>>CV[i]; memset(F,0,sizeof(F)); for(int i=1;i<=n;i++) { for(int v=0;v<=V;v++) { int maxiv = F[i-1][v]; for(int k=1;k<= NV[i];k++) { int wik = CV[i]*k; if( v - wik < 0) break; int ivk = F[i-1][v-wik] + wik; if(ivk > maxiv) maxiv= ivk; } F[i][v] = maxiv; } } cout<<F[n][V]<<endl; } } 按照前辈思路优化后: #include <iostream> #include <stdio.h> #include <cstring> using namespace std; //多重背包为题 //动态方程 //F[i][v] = max{ F[i-1][V-vi*k] + k*ci} //放入k个v k从0到ni ni为i物品的个数 F[i][v] // //F[i][v] 为第i个物品能够取得容量为v // // //初始值 //F[ int V,n; #define MAX_V (100000 +1) #define MAX_N (10+1) bool F[MAX_V]; //F[i]表示能否获得F[i] int NV[MAX_N]; int CV[MAX_N]; int main() { while(scanf("%d%d",&V,&n) != EOF) { for(int i=1;i<=n;i++) scanf("%d%d",&NV[i],&CV[i]); //cin>>NV[i]>>CV[i]; memset(F,0,sizeof(F)); F[0]=true; int maxcash = 0; for(int i=1;i<=n;i++) { for(int c=maxcash;c>=0;c--) { if(F[c]) { for(int k=1;k<=NV[i];k++) { int kcash = c + k*CV[i]; if(kcash > V) break; F[kcash]=true; if(kcash > maxcash) maxcash = kcash; } } } } for(int j=V;j>=0;j--) { if(F[j]) { cout<<j<<endl; break; } } } } 或者进行二进制切分,即将价值为k有6份的物品,拆分为键值为k1,k2,k3的三种物品,每种物品数量为1,2,3,之后进行01背包问题求解 具体拆分请看 背包问题九讲 Source Code Problem: 1276 User: csjiaxin Memory: 632K Time: 47MS Language: C++ Result: Accepted Source Code #include <iostream> #include <stdio.h> #include <cstring> using namespace std; //多重背包为题 //动态方程 //F[i][v] = max{ F[i-1][V-vi*k] + k*ci} //放入k个v k从0到ni ni为i物品的个数 F[i][v] // //F[i][v] 为第i个物品能够取得容量为v // // //初始值 //F[ int V,n; #define MAX_V (100000 +1) #define MAX_N (100000+1) int F[MAX_V]; //F[i]表示能否获得F[i] int NV[MAX_N]; int CV[MAX_N]; int cnt; //二进制拆分 #define printf // int main() { while(scanf("%d%d",&V,&n) != EOF) { memset(F,0,sizeof(F)); cnt = 0; for(int i=1;i<=n;i++) { int in,ic; scanf("%d%d",&in,&ic); //cin>>NV[i]>>CV[i]; int left = 0; int k; printf("in=%d,ic=%d\n",in,ic); for(k=1;k<=in;k *= 2) { printf("k=%d kc=%d cnt=%d\n",k,ic*k,cnt); CV[cnt++] = ic * k; //left = in-k; in -= k; } if(in > 0) { CV[cnt++] = ic *(in ); printf("k=%d kc=%d\n",in,in*ic); } } //进而用01背包求解 for(int i=0;i<cnt;i++) { for(int c=V;c>=CV[i];c--) { int ci_1 = F[c-CV[i]] + CV[i]; printf("i=%d,c-CV[i]=%d F[]=%d ci_1=%d\n",i,c-CV[i],F[c-CV[i]],ci_1); if(F[c] < ci_1) { F[c] = ci_1; printf("set F[%d]=%d\n",c,F[c]); } } } int maxv= -1; for(int j=V;j>=0;j--) { if(F[j] > maxv) { maxv=F[j]; } } cout<<maxv<<endl; } }

上一篇:STL中mem_fun和mem_fun_ref的用法
下一篇:[置顶] C++ 虚函数表解析(转载)

相关文章

相关评论