HDU ACM 2844 Coins (多重背包)----------------01背包,完全背包,多重背包模板-白红宇

HDU ACM 2844 Coins (多重背包)----------------01背包,完全背包,多重背包模板

阅读量：5164 次

发布时间：2019-06-13

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

多重背包问题.

求出恰好能买的数目.最后找f[i]>0的背包有几个

或者

不需要恰好装满,最后搜索f[i] == i 的数目

//背包模版

1 #include 
      
        2 using namespace std; 3 const int MAX = 100000 + 10; 4 const int INF = 0x7fffffff; 5 int f[MAX]; 6 int v; 7 void ZeroOnePack(int cost,int weight) 8 { 9     int i;10     for(i=v;i>=cost;i--)11     {12         f[i] = max(f[i],f[i-cost]+weight);13     }14 }15 void CompletePack(int cost,int weight)16 {17     int i;18     for(i=cost;i<=v;i++)19     {20         f[i] = max(f[i],f[i-cost]+weight);21     }22 }23 void MultiplePack(int cost,int weight,int amount)24 {25     if(v <= cost*amount)26     {27         CompletePack(cost,weight);28         return;29     }30     else31     {32         int k = 1;33         while(k
       
        >n>>v,n+v)46     {47         int c[MAX];48         int a[MAX];49         int i;50         for(i=0;i
        
         >c[i];53         }54         for(i=0;i
         
          >a[i];57         }58         for(i=0;i<=v;i++)59         {60             f[i] = -1*INF;61         }62         f[0] = 0;63         for(i=0;i
          
            0)71             {72                 sum++;73             }74         }75         cout<
           
            <