背包模版

关于背包DP的文章很多，谷歌百度搜《背包九讲》即可。本文章只放模版。

文章统一v代表体积，w代表价值，f代表dp数组，V代表总体积，W代表总价值，均采用滚动数组。答案一般都为f[V]。

• 01背包：
  
  ?

  1 2 3 4

  void zop(int v, int w) {     for(int i = V; i >= v; --i)         f[i] = max(f[i], f[i-v]+w); }

• 完全背包：
  
  ?

  1 2 3 4

  void cmp(int v, int w) {     for(int i = v; i >= V; ++i)         f[i] = max(f[i], f[i-v]+w); }

• 多重背包：
  
  ?

  1 2 3 4 5 6 7 8 9 10

  void dcp(int v, int w, int m) {     if(m * v >= V) { cmp(v, w); return; }     int k = 1;     while(k < m) { //二进制思想，即倍增         zop(k*v, k*w);         m -= k;         k <<= 1;     }     zop(m*v, m*w); }

• 多维背包（原理都一样的）：
  
  ?

  1 2 3 4 5 6 7 8

  //多维的话，增加滚动数组维数，例如有两个约束G和V，那么可以这样（这是多维的01） int i, j, k; for(i = 1; i <= N; ++i) {     cin >> v >> g >> w;     for(j = V; j >= v; --v)         for(k = G; k >= g; --k)             f[j][k] = max(f[j][k], f[j-v][k-g]+w); }

• 混合背包：
  
  ?

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

  void zop(int v, int w) {     for(int i = V; i >= v; --i)         f[i] = max(f[i], f[i-v]+w); }   void cmp(int v, int w) {     for(int i = v; i >= V; ++i)         f[i] = max(f[i], f[i-v]+w); }   void dcp(int v, int w, int m) {     if(m * v >= V) { cmp(v, w); return; }     int k = 1;     while(k < m) { //二进制思想，即倍增         zop(k*v, k*w);         m -= k;         k <<= 1;     }     zop(m*v, m*w); }

背包模版

原文：http://www.cnblogs.com/iwtwiioi/p/3538766.html