リュックサックまとめ

n種類の品物と容量vのリュックサックがあります.i番目のアイテムはMi(Mi=1,k,INF)(01,完全,多重)が利用可能であり,1件あたりの消費空間はCiであり,価値はWiである.リュックサックにどのアイテムを入れると、これらのアイテムの消費スペースの合計がリュックサックの容量を超えず、価値の合計が最大になるかを解きます.
リュック初期化:ちょうど満タン:dp[0]=0,dp[1~n]=-INF;(負無限)満タンにする必要はありません:dp[0~n]=0;
1.01リュックサック

for(int i=1;i<=n;i++)
    for(int j=v;j>=c[i];j--)
    dp[j]=max(dp[j-c[i]+w[i],dp[j]);

2.完全リュック

for(int i=1;i<=n;i++)
    for(int j=c[i];j<=v;j++)
    dp[j]=max(dp[j-c[i]+w[i],dp[j]);

3.多重バックパック
バイナリ分解O(N*&Mi)(&MiはM 1+M 2+......Mn)

void ZeroOnePack(int cost,int wei)//01 
{  
    int i;  
    for(i = v;i>=cost;i--)  
    {  
        dp[i] = max(dp[i],dp[i-cost]+wei);  
    }  
}  

void CompletePack(int cost,int wei)//   
{  
    int i;  
    for(i = cost;i<=v;i++)  
    {  
        dp[i] = max(dp[i],dp[i-cost]+wei);  
    }  
}  

void MultiplePack(int cost,int wei,int cnt)//   
{  
    if(v<=cnt*cost)//               ，            ，        
    {  
        CompletePack(cost,wei);  
        return ;  
    }  
    else//           01   
    {  
        int k = 1;  
        while(k<=cnt)  
        {  
            ZeroOnePack(k*cost,k*wei);  
            cnt = cnt-k;  
            k = 2*k;  
        }  
        ZeroOnePack(cnt*cost,cnt*wei);  
    }  
} 

単調キューO(NV):
詳しくは:多重バックパックの説明

const int MAX_V = 100004;  
//v、n、w：             、  、   
//V：    ， MAX_V：         
//f[i]：   i         ，        。 
inline void pack(int f[], int V, int v, int n, int w)  
{  
  if (n == 0 || v == 0) return;  
  if (n == 1) {               //01   
    for (int i = V; i >= v; --i)  
      if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;  
    return;  
  }  
  if (n * v >= V - v + 1) {   //    (n >= V / v) 
    for (int i = v; i <= V; ++i)  
      if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;  
    return;      
  }  

  int va[MAX_V], vb[MAX_V];   //va/vb:  /     
  for (int j = 0; j < v; ++j) {     //     
    int *pb = va, *pe = va - 1;     //pb/pe       /    
    int *qb = vb, *qe = vb - 1;     //qb/qe         /    
    for (int k = j, i = 0; k <= V; k += v, ++i) {  
      if (pe  == pb + n) {       //          ，     X  。 
        if (*pb == *qb) ++qb;   //            X，      。 
        ++pb;  
      }  
      int tt = f[k] - i * w;  
      *++pe = tt;                  //  X   
      //          X   ，qb qe    ，        
      while (qe >= qb && *qe < tt) --qe;  
      *++qe = tt;              //  X         
      f[k] = *qb + i * w;      //                      
    }  
  }  
}  

4.二次元リュック

for(int i=0;i<k;i++)  { for(int v=value[i][1];v<=m;v++) { for(int b=1;b<=s;b++) { dp[v][b]=dp[v][b]>dp[v-value[i][1]][b-1]+value[i][0]?dp[v][b]:dp[v-value[i][1]][b-1]+value[i][0];
 if(dp[v][b]>=n&&m-v>=cost)
 {
 cost=m-v;
 }
 } 
 } 
 }
 if(dp[m][s]<n)printf("-1
");
 else
 printf("%d
",cost);
  }

4.リュックサックのグループ分け

for(int i=1;i<=N;i++)
   for(int j=V;j>=0;j--)
       for(int k=1;k<=j;k++)
        f[j]=max(f[j],f[j-k]+A[i][k]);

詳しくは「リュックサック九講」を参照してください.