多重背包题目-白红宇

多重背包题目

阅读量：4969 次

发布时间：2019-06-12

本文共 6303 字，大约阅读时间需要 21 分钟。

pku 1276 Cash Machine

题意：

自动取款机里面的最大存钱量为cash，现在有n种不同价值的纸币，每个都有一定的数量，问这些纸币能够组合出来的小于等于cash的最大值。

思路：

典型的多重背包，转换01思想的做法TLE，只能用二进制倍增优化。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 1000007#define N 12using namespace std;//freopen("din.txt","r",stdin);int c[N],n[N];int f[M];void zb(int c,int V){ for (int i = V; i >= c; --i) f[i] = f[i]|f[i - c];}void cb(int c,int V){ for (int i = c; i <= V; ++i) f[i] = f[i]|f[i - c];}int main(){ //freopen("din.txt","r",stdin); int cash; int i,ni; while (~scanf("%d",&cash)){ scanf("%d",&ni); for (i = 0; i < ni; ++i){ scanf("%d%d",&n[i],&c[i]); } CL(f,0); f[0] = 1; for (i = 0; i < ni; ++i){ if (n[i]*c[i] > cash){ cb(c[i],cash); } else{ int k = 1; while (k < n[i]){ zb(k*c[i],cash); n[i] -= k; k <<= 1; } zb(n[i]*c[i],cash); } } for (i = cash; i >= 0; --i) if (f[i]) break; printf("%d\n",i); } return 0;}

pku 1014 Dividing

题意：

有六种大理石，他们对应的价值分别为1,2,3,4,5,6. 给出每种大理石的个数，问我们是否能够将他们等分成价值相等的两份。

思路：

完全背包+二进制倍增优化。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 5000007#define N 7using namespace std;//freopen("din.txt","r",stdin);int f[M];int c[N];void zb(int c,int V){ for (int i = V; i >= c; --i) f[i] |= f[i - c];}void cb(int c,int V){ for (int i = c; i <= V; ++i) f[i] |= f[i - c];}int main(){ //freopen("din.txt","r",stdin); int i; int cas = 1; while (~scanf("%d%d%d%d%d%d",&c[0],&c[1],&c[2],&c[3],&c[4],&c[5])){ if (!c[0] && !c[1] && !c[2] && !c[3] && !c[4] && !c[5]) break; printf("Collection #%d:\n",cas++); int V = 0; for (i = 0; i < 6; ++i) V += c[i]*(i + 1); if (V&1){ puts("Can't be divided."); printf("\n"); continue; } V /= 2; for (i = 0; i <= V; ++i) f[i] = 0; f[0] = 1; for (i = 0; i < 6; ++i){ if (c[i]*(i + 1) > V) cb(i + 1,V); else{ int k = 1; while (k < c[i]){ zb(k*(i + 1),V); c[i] -= k; k <<= 1; } zb(c[i]*(i + 1),V); } } //printf("%d %d\n",V,f[V]); if (f[V]) puts("Can be divided."); else puts("Can't be divided."); printf("\n"); } return 0;}

pku 2392 Space Elevator 可行性判断+贪心

题意：

奶牛想上太空给顶n种梯子，每种梯子对应三个值，a,h,c，a表示这种梯子必须在小于等于a的高度内使用，h表示它的高度，c表示这种梯子的个数。问内牛能够累出的最大高度。

思路：

O（N*V）可行性判断+按a从小到大贪心选择

View Code

pku 1742 Coins

题意：

.有n中面值不同的硬币，他们的价值，数量非别给出，求他们能够组合出来的小于等于m的价值数；

思路：

楼爷的经典题目，多重背包可行性优化O（N*V）

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 100007#define N 107using namespace std;//freopen("din.txt","r",stdin);int f[M],c[N],w[N];int cnt[M];int main(){ //freopen("din.txt","r",stdin); int i,j; int n,m; while (~scanf("%d%d",&n,&m)){ if (!n && !m) break; for (i = 0; i < n; ++i) scanf("%d",&w[i]); for (i = 0; i < n; ++i) scanf("%d",&c[i]); for (i = 0; i <= m; ++i) f[i] = 0; f[0] = 1; int ans = 0; for (i = 0; i < n; ++i){ for (j = 0; j <= m; ++j) cnt[j] = 0; for (j = 0; j <= m - w[i]; ++j){ if (f[j] && !f[j + w[i]] && cnt[j] < c[i]){ f[j + w[i]] = 1; cnt[j + w[i]] = cnt[j] + 1; ans++; } } } printf("%d\n",ans); }}

pku 1787 Charlie's Change (zoj2156)

多重背包记录选择的物品的个数

题意：

有面值为1,5,10,20的四种硬币，非别给出他们的数量问他是否能够组合出面值为P的价值，若果可以输出他的方案，如果存在多种方案输出使用硬币数最多的。

思路：

O（N*V）优化多重背包的可行性求解，这里主要是开一个二维数组num[i][j]表示i状态下装了第j中硬币多少个。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a , b) ((a) < (b) ? (a) : (b))#define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 10007#define N 4using namespace std;//freopen("din.txt","r",stdin);int f[M],num[M][N];int c[N],cnt[M];int val[4] = { 1,5,10,25};int main(){ //freopen("din.txt","r",stdin); int V,i,j; while (~scanf("%d%d%d%d%d",&V,&c[0],&c[1],&c[2],&c[3])){ if (!V && !c[0] && !c[1] && !c[2] && !c[3]) break; CL(num,0); for (i = 0; i <= V; ++i) f[i] = 0; f[0] = 1; for (i = 0; i < 4; ++i){ for (j = 0; j <= V; ++j) cnt[j] = 0; for (j = 0; j <= V - val[i]; ++j){ if (f[j] && cnt[j] < c[i]){ int a = j + val[i]; if (!f[a]){ f[a] = 1; cnt[a] = cnt[j] + 1; //将上一个状态转移下来 for (int k = 0; k < 4; ++k){ num[a][k] = num[j][k]; } num[a][i]++; } else{ int s1 = 0,s2 = 0; for (int k = 0; k < 4; ++k){ s1 += num[j][k]; s2 += num[a][k]; } //存在多种方案去最大的 if (s2 < s1 + 1){ for (int k = 0; k < 4; ++k){ num[a][k] = num[j][k]; } num[a][i]++; } } } } } if (f[V]){ printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",num[V][0],num[V][1],num[V][2],num[V][3]); } else{ puts("Charlie cannot buy coffee."); } } return 0;}

更新中.......

转载于:https://www.cnblogs.com/E-star/archive/2012/10/10/2718761.html

你可能感兴趣的文章