背包模板-白红宇

背包模板

阅读量：5361 次

发布时间：2019-06-15

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

/*多重背包模板【若要求恰好装满,初始化时f[1...V] = -INF(求最大)或INF(求最小),f[0] = 0】【若费用==价值时，如硬币能组成多少钱，用背包做时，f[i(费用)] 必定 == i(最大价值) （设能组成i元）  ，因为能组成i元。费用为i时，最大价值若少于i的x的话与能组成i元，矛盾(存在比x大的i),所以必定等于i元,如HDU2844】*/#include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         using namespace std;//Constant Declaration/*--------------------------*///#define LL long long#define LL __int64const int M=110;const int INF=1<<30;const double EPS = 1e-11;const double PI = acos(-1.0);/*--------------------------*/// some essential funtion/*----------------------------------*/void Swap(int &a,int &b){ int t=a;a=b;b=t; }int Max(int a,int b){ return a>b?a:b; }int Min(int a,int b){ return a
                         
                          = c; v--) { f[v] = Max(f[v], f[v-c] + w); }}//完全背包void CompletePack(int c, int w){ for (int v = c; v <= V; v++) { f[v] = Max(f[v], f[v-c] + w); }}//多重背包，二进制。void MultiplePack(int c, int w, int n1){ if (c * n1 >= V) { CompletePack(c, w); } else { int k = 1; while (k < n1) { ZeroOnePack(k*c, k*w); n1 -= k; k <<= 1; } ZeroOnePack(n1*c, n1*w); }}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t, case1 = 0; scanf("%d", &t); int n, m;//n:物品种数 int i, j; //scanf("%d%d", &n, &m); while (t--) { scanf("%d%d", &V, &n); for (i = 1; i <= n; i++) { scanf("%d%d%d", &c[i], &w[i], &n1[i]); } memset(f, 0, sizeof(f)); for (i = 1; i <= n; i++) { MultiplePack(c[i], w[i], n1[i]); } printf("%d\n", f[V]); } return 0;}