背包九讲学习笔记

1：01背包

问题描述

• 有\(n\)件物品以及容量为\(m\)的背包。第\(i\)件物品的体积是\(v(i)\)，价值是\(w(i)\)，求物品装入背包总价值最大。

思路

• 设\(f(i,j)\)表示考虑前\(i\)件物品且背包体积为\(j\)时可以得到的最大价值，有状态转移方程：
  • \(f(i,j)=max(f(i-1,j),f(i-1,j-v(i))+w(i))\).
• 也就是考虑一件物品放或者不放，有两种选择。
• 不放第\(i\)件物品就是\(f(i-1,j)\)，这个很好理解；而放第\(i\)件物品就是将第\(i\)件物品放入\(j-v(i)\)时，容量为\(j\)的背包能获得的最大值，也就是\(f(i-1,j-v(i))+w(i))\)。

优化

• 上述方法的时间复杂度为\(O(nm)\)，时间复杂度无法再优化了，但是空间复杂度可以。

• 仔细观察转移方程，可以发现，第\(i\)个状态，都是从\(i-1\)的状态转移过来，所以我们可以从这个方向优化掉一维的空间复杂度。
• 于是有状态转移方程：\(f(j)=max(f(j),f(j-v(i))+w(i))\)。

• 这样的优化叫做滚动数组。

例题：acw2:01背包

• 如果用最原始的转移方程有：

• cin >> m >> n;
  for(int i = 1; i <= n; i++)
      scanf("%d%d", &v[i], &w[i]);
  for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
  {
      f[i][j] = max(f[i-1][j], f[i][j]);
      if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
  }
  cout << f[n][m] << endl;

• 优化一维之后变为：

• cin >> m >> n;
  for(int i = 1; i <= n; i++)
      scanf("%d%d", &v[i], &w[i]);
  for(int i = 1; i <= n; i++)
      for(int j = m; j >= v[i]; j--)
          f[j] = max(f[j], f[j-v[i]]+w[i]);
  cout << f[m] << endl;

• 复杂度为\(O(nm)\)。

• 这里有个小问题，就是在第二维循环的时候体积是从大到小枚举的，至于原因在下一节完全背包解释。

初始化问题

• 刚刚这种求解最优化情况的时候，没有对\(f\)数组初始化有什么要求，但是有的题目要求"恰好装满背包"，有的题目不要求恰好装满背包。这两种问法在初始化上有一些不同。
  • 如果没有要求恰好装满背包，只希望价值尽量的大，那么初始化为\(0\)就可以了。
  • 如果要求恰好装满背包的情况下：
    • 如果求最大值时，那就要求\(f(0)=0\)，其他的均为\(-\infin\)。
    • 如果求最小值时，那就要求\(f(0)=0\)，其他的均为\(+\infin\)。
• 可以这样理解，初始化\(dp\)使用的数组事实上就是没有任何物品放入背包时的状态。如果要求背包恰好装满，那么此时只有容量为\(0\)的背包可以在什么也不装的情况下"恰好装满"，此时背包价值为\(0\)，其余容量的背包均没有合法的解，属于未定义的状态，所以赋值无穷小/大。
• 如果不要求“恰好装满”，那么任何容量的背包都有一个合法解“什么也不装”，这个解的价值为\(0\)，所以初始化状态值全部为\(0\)。

2：完全背包

问题描述

• 有\(n\)种物品和容量为\(m\)的背包，每种物品都可以无限次的使用，其中第\(i\)件物品价值为\(w(i)\)，体积为\(v(i)\)。问装入背包的方案中价值最大的那个的价值。

思路

• 完全背包比较类似于01背包，但是又有所不同。相同的地方在于他们都是考虑每个物品取，或者是不取，但是不同的地方在于完全背包要考虑取0件，1件，2件，3件，...等。
• 所以我们先来按照01背包的思路设计状态转移方程。
• \(f(i,j)=max(f(i-1,j-k*v(i))+k*w(i))\)。
• k是系数，也就是拿0件，1件，2件，...等这样的方案。
• 这样的话我们需要枚举\(O(n^3)\)，效率不高。
• 考虑一个神奇的优化：
  • \(f(i,j)=max(f(i-1,j),f(i-1,j-v)+w,f(i-1,j-2v)+2w,f(i-1,j-3v)+3w,...)\)
  • \(f(i,j-v)=max(f(i-1,j-v),f(i-1,j-2v)+w,f(i-1,j-3v)+2w...))\)
  • 我们发现\(f(i,j-v)+w\)，其实就是第一个式子的后面的部分，所以可以优化成：
  • \(f(i,j)=max(f(i-1,j),f(i,j-v)+w)\)。
  • 这就是完全背包的最后的状态转移方程。
• 比较01背包的状态转移方程：\(f(i,j)=max(f(i-1,j),f(i-1,j-v)+w)\)，发现其实是非常相似的。

优化

• 优化空间复杂度：\(f(j)=max(f(j-v)+w)\)。

例题：acw3:完全背包

• 完全背包板子题，首先看朴素的写法。

• for(int i = 1; i <= n; i++)
      for(int j = 0; j <= m; j++)
      {
          f[i][j] = max(f[i][j], f[i - 1][j]);
          if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
      }
  cout << f[n][m] << endl;

• 滚动数组写法。

• for(int i = 1; i <= n; i++)
          for(int j = v[i]; j <= m; j++)
              f[j] = max(f[j], f[j - v[i]] + w[i]);
  cout << f[m] << endl;

• 复杂度为\(O(nm)\)。

• 这里给出01背包的滚动数组写法：

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

• 我们可以发现，01背包是逆序循环的，完全背包是顺序循环的。

顺序枚举与逆序枚举的区别

• 首先看正序枚举。
• 假设我现在有一个体积为3，价值为4的物品，正序循环。

• 

• 在此时体积为3的背包有了一个价值为4的物品
• 接着循环。

• 

• 到体积为6的背包时候，价值就会变成\(f(6)=f(6-3)+4=8\)。
• 也就是说，同一个物品，我用了两遍。
• 所以完全背包使用正序循环，这样一种物品就可以使用多次。
• 接着看倒序枚举。

• 

• 在体积为6的时候，\(f(6)=f(6-3)+4=4\).
• 接着循环到体积为3的时候，\(f(3)=f(3-3)+4=4\)。

• 

• 也就是说对于这样一个体积为3的物体，不管背包容量是多少，物品只用了一次。
• 所以01背包采用逆序循环。
• 总结一下：
  • 倒序：物品使用一次。
  • 正序：物品使用多次。

3：多重背包

题目描述

• 有\(n\)种物品和一个容量为\(m\)的背包，其中第\(i\)种物品有\(c_i\)个，要求选择若干物品装入背包使得背包内总价值最大。

多重背包1acw4

• 我们同样可以先用01背包的相似思路思考，考虑每个物品使用1次，2次，3次，...

• 设\(f(i,j)\)表示

• 那么就有状态转移方程：\(f(i,j)=max(f(i-1,j)f,(i-1,j-k*v(i))+w(i))\)，其中\(1\leq k\leq c_i\)。

• 附上代码：

• for(int i = 1; i <= n; i++) 
          scanf("%d%d%d", &v[i], &w[i], &c[i]);
      for(int i = 1; i <= n; i++)
          for(int j = 0; j <= m; j++)
            for(int k = 1; k <= c[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k*v[i]] + w[i] * k);
      cout << f[n][m] << endl;

• 采用滚动数组优化空间。

• for(int i = 1; i <= n; i++) 
      scanf("%d%d%d", &v[i], &w[i], &c[i]);
  for(int i = 1; i <= n; i++)
      for(int j = m; j >= v[i]; j--)
          for(int k = 1; k <= c[i] && k * v[i] <= j; k++)
              f[j] = max(f[j], f[j-k*v[i]]+k*w[i]);
  cout << f[m] << endl;

• 此法较为简单，易于思考，可惜效率不高。

• 时间复杂度：\(O(nmc)\)

多重背包2acw5

• 二进制拆分：由二进制的知识可以知道，任意一个整数可以由二次幂数字相加而得，所以可以用此方法把\(c_i\)件物品拆分成\(logc_i\)件物品。

• 这样的话我们需要先需要将\(n\)件物品先拆分成\(nlogc\)件物品，然后用01背包的方法写出。

• 代码如下：

• scanf("%d%d", &n, &m);
  int cnt = 0;
  for(int i = 1, vv, ww, cc; i <= n; i++)
  {
      scanf("%d%d%d", &vv, &ww, &cc);
      int k = 1;
      while(k <= cc)
      {
          v[++cnt] = vv * k;
          w[cnt] = ww * k;
          cc -= k; k *= 2;
      }
      if(cc > 0)
      {
          v[++cnt] = vv * cc;
          w[cnt] = ww * cc;
      }
  }
  n = cnt;
  for(int i = 1; i <= n; i++)
      for(int j = m; j >= v[i]; j--)
          f[j] = max(f[j], f[j-v[i]]+w[i]);
  cout << f[m] << endl;

• 时间复杂度\(O(nmlogc)\)。

多重背包3acw6

• 使用单调队列，可以进一步的优化成\(O(nm)\)。
• 我们先看最朴素的方程：
• \(f(i,j)=max(f(i-1,j),f(i-1,j-k*v(i))+w(i))\).
• 滚动一下：\(f(j)=max(f(j),f(j-k*v(i)))\)。
• 此时画图来模拟一下\(dp\)的过程。

• 

• 当循环变量\(j\)减小\(1\)时：

• 

• 可以发现，相邻的两个状态\(j\)和\(j-1\)对应的决策集合没有重叠。很难快速的从\(j-1\)状态对应到\(j\)状态。
• 但是如果考虑\(j\)和\(j-v_i\)呢？如图：

• 

• \(j\)和\(j-v\)这两个状态之间，决策集合重叠较多，而我们对于一层循环而言，我们找的就是\(max(f(j-k*v(i)))\)，对于这样一个重合较多的集合，我们应该能联想到使用单调队列动态的求一段窗口内的最大值，也就是滑动窗口。
• 同时我们发现\(j\)和\(j-1\)是两个互不影响的两者决策集合。
• 所以我们将状态\(j\)按照模\(v_i\)的余数分组，对每一组分别计算。
  • 余数为\(0\)——\(0,v_i,2v_i,...\)
  • 余数为\(1\)——\(1,1+v_i,1+2v_i,...\)
  • \(...\)
  • 余数为\(v_i-1\)——\(v_i-1,(v_i-1)+v_i,(v_i-1)+2v_i,...\)

• 代码如下：

• #include<bits/stdc++.h>
  using namespace std;
  const int maxm = 20000 + 10;
  int n, m;
  int f[maxm], q[maxm], g[maxm];
  
  int main()
  {
      scanf("%d%d", &n, &m);
      for(int i =  1, v, w, c; i <= n; i++)
      {
          scanf("%d%d%d", &v, &w, &c);
          memcpy(g, f, sizeof(f));
          //滚动数组优化空间 f[] = f[i-1][];
          for(int j = 0; j < v; j++)
          {
              int hh = 0, tt = -1;
              for(int k = j; k <= m; k += v)
              {
                  f[k] = g[k];
                  //如果窗口的内容超过了c[i]个, 出队
                  if(hh <= tt && k-c*v > q[hh]) 
                      hh++; 
                  if(hh <= tt) //max(f(i-1,k), f(i-1,能转移里最大)+个数*w[i])
                      f[k] = max(f[k], g[q[hh]]+(k-q[hh])/v*w);  
                  while(hh <= tt && g[q[tt]]-(q[tt]-j)/v*w <= g[k]-(k-j)/v*w) 
                      tt--;
                  q[++tt] = k;
              }
          }
      }
      cout << f[m] << endl;
      return 0;
  }

• 时间复杂度\(O(nm)\)。

4：混合背包acw7

• 混合背包就是上述三种背包的混合

题目描述

• 有\(n\)种物品和一个体积为\(m\)的背包，物品一共有三类：
  • 第一类物品只能用1次。（01背包）
  • 第二类物品可以用无限次。（完全背包）
  • 第三类物品最多可以用\(s_i\)次。（多重背包）
• 每种物品体积为\(v_i\)，价值为\(w_i\)。
• 求解价值最大。

思路

• 就分类讨论就行了，不是那么困难。

• 但是还是要区分一下，这一题的数据允许使用二进制拆分，二进制拆分后用01背包跑，所以01背包可以和多重背包混成一个条件，但是01和完全背包是不一样的，所以需要记录来区分一下。

• 当然要注意的是二进制拆分过后点数量多了\(log\)的级别，所以数组要开大一点。

• 代码：

• #include<bits/stdc++.h>
  using namespace std;
  const int maxn = 5e5 + 10;
  int n, m, v[maxn], w[maxn], s[maxn], f[maxn], cnt;
  int main()
  {
      scanf("%d%d", &n, &m);
      for(int i = 1, vv, ww, cc; i <= n; i++)
      {
          scanf("%d%d%d", &vv, &ww, &cc);
          if(cc < 0) //01
          {
              v[++cnt] = vv;
              w[cnt] = ww;
              s[cnt] = 1;
          }
          else if(cc == 0) //完全
          {
              v[++cnt] = vv;
              w[cnt] = ww;
              s[cnt] = 0;
          }
          else if(cc > 0) //多重
          {
              int k = 1;
              while(k <= cc)
              {
                  v[++cnt] = vv * k;
                  w[cnt] = ww * k;
                  cc -= k; k *= 2;
                  s[cnt] = 1;
              }
              if(cc > 0)
              {
                  v[++cnt] = vv * cc;
                  w[cnt] = ww * cc;
                  s[cnt] = 1;
              }
          }
      }
  
      n = cnt;
      for(int i = 1; i <= n; i++)
      {
          if(s[i] == 1)
          {
              for(int j = m; j >= v[i]; j--)
                  f[j] = max(f[j], f[j-v[i]]+w[i]);
          }
          else
          {
              for(int j = v[i]; j <= m; j++)
                  f[j] = max(f[j], f[j-v[i]]+w[i]);
          }
      }
      cout << f[m] << endl;
      return 0;
  }

5：二维费用背包问题acw8

问题描述

• 有\(N\)件物品和一个容量为\(V\)的背包，背包承重最大重量是\(M\)。
• 每件物品只能用一次。体积是\(v_i\)，重量是\(m_i\)，价值是\(w_i\)。
• 问将物品装入背包，体积和重量不可超，价值最大总和是多少？

思路

• 限制条件增多了一个维度，也就是重量，状态也只需要增加一个维度即可。

• 设\(f(i,j,k)\)表示前\(i\)件物品中，体积为\(j\)，重量为\(k\)的物品能获得的最大的价值。

• 转移方程有\(f(i,j,k)=max(f(i,j,k),f(i-1,j-v(i),k-m(i))+w(i))\).

• 滚动一下的话可以取消掉第一维也就是\(i\)这一维，代码如下：

• scanf("%d%d%d", &N, &V, &M);
  for(int i = 1; i <= N; i++)
      scanf("%d%d%d", &v[i], &m[i], &w[i]);
  for(int i = 1; i <= N; i++)
      for(int j = V; j >= v[i]; j--)
          for(int k = M; k >= m[i]; k--)
              f[j][k] = max(f[j][k], f[j-v[i]][k-m[i]]+w[i]);
  cout << f[V][M] << endl;

题意描述

• 有\(n\)组物品和一个容量为\(m\)的背包，每组物品有\(c_i\)个，同一组物品最多只能选一个。
• 每件物品的体积是\(v_{ij}\)，价值是\(w_{ij}\)，其中\(i\)是组号，\(j\)是组内编号。
• 求解将物体装入背包，体积和不超过背包容量，总价值最大。

思路

• 分情况讨论，分为不选第\(i\)组的物品和选第\(i\)组的第\(j\)个物品。

• scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++)
  {
      scanf("%d", &c[i]);
      for(int j = 1; j <= c[i]; j++)
            scanf("%d%d", &v[i][j], &w[i][j]);
  }
  
  for(int i = 1; i <= n; i++)
    for(int j = m; j >= 0; j--)
        for(int k = 1; k <= c[i]; k++)
            if(j >= v[i][k])
                f[j] = max(f[j], f[j-v[i][k]]+w[i][k]);
  cout << f[m] << endl;

7：有依赖的背包问题acw10

问题描述：

• 有\(n\)个物品和一个容量为\(m\)的背包。
• 物品之间有依赖关系，且依赖关系成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
• 图示：
• 每件物品的体积是\(v_i\)，价值是\(w_i\)，父节点编号是\(p_i\)。
• 求解价值最大。

思路：

• 其实这是树型+背包问题的一个结合，也就是树上背包。

• 假设说\(1\)号节点是\(2\)号节点的父节点，那么对于\(2\)节点及其子树构成一组物品，对于\(2\)号节点有许多种体积的子背包，对于\(1\)号节点而言，他只能从这许多种体积的子背包中选一个加入自己的背包中，而\(1\)号节点有可能有许多个子节点，所以其实是树上分组背包。

• 设\(f(i,j)\)表示在选节点\(i\)的情况下并且背包体积为\(j\)的情况下，以\(i\)为根的整棵子树的最大收益是多少。

• 对树进行\(dfs\)即可。

• int head[maxn<<1], ver[maxn<<1], nex[maxn<<1], tot;
  inline void add_edge(int x, int y){
      ver[++tot] = y; nex[tot] = head[x]; head[x] = tot;
  }
  
  void dfs(int x)
  {
      for(int i = head[x]; i; i = nex[i])
      {
          int y = ver[i]; dfs(y);//递归求出儿子的方案
          for(int j = m-v[x]; j >= 0; j--) //分组背包
              for(int k = 0; k <= j; k++) //选择一个子节点的k体积的子背包
                  f[x][j] = max(f[x][j], f[x][j-k]+f[y][k]);
      }
      //加上根节点的价值
      for(int i = m; i >= v[x]; i--) f[x][i] = f[x][i-v[x]]+w[x];
      for(int i = 0; i < v[x]; i++) f[x][i] = 0; //体积不够选不了
  }
  
  int main()
  {
      scanf("%d%d", &n, &m);
      for(int i = 1, p; i <= n; i++)
      {
          scanf("%d%d%d", &v[i], &w[i], &p);
          if(p == -1) root = i;
          else add_edge(p, i);
      } dfs(root);
      cout << f[root][m] << endl;
      return 0;
  }

8：背包问题求方案数acw11

问题描述：

• 给定\(n\)件物品和一个容量为\(m\)的背包，每件物品至多使用一次。
• 第\(i\)件物品体积为\(v_i\)，价值为\(w_i\)。
• 问最优选法的方案数，结果模\(10^9+7\)。

思路：

• 设\(f(j)\)表示背包体积为\(j\)的最优方案的价值。

• 设\(d(j)\)表示背包体积为\(j\)的最优解方案数。

• 初始化\(d(i)=1\)，因为什么也不装也是一种方案。

• ll f[maxn], d[maxn];
  int n, m, v[maxn], w[maxn];
  int main()
  {
      scanf("%d%d", &n, &m);
      for(int i = 1; i <= n; i++)
          scanf("%d%d", &v[i], &w[i]);
      for(int i = 0; i <= m; i++) d[i] = 1;
      for(int i = 1; i <= n; i++)
      {
          for(int j = m; j >= v[i]; j--)
          {
              ll tmp = f[j-v[i]] + w[i];
              if(tmp > f[j]) 
              {
                  f[j] = tmp;
                  d[j] = d[j-v[i]];
              }
              else if(tmp == f[j])
                  d[j] = (d[j] + d[j-v[i]]) % mod;
          }
      }
      cout << d[m] << endl;
      return 0;
  }

9：背包问题求具体方案acw12

题意描述：

• \(n,m\)表示物品数和背包容积，每个物品用一次。
• \(v_i,w_i\)表示体积价值。
• 求解最优解的最小字典序的方案。

思路：

• 最后结果是\(f(n,m)\)。
• 如果\(f(n,m)=f(n-1,m)\)说明最后一个物品没有选。

• 当然如果\(f(n,m)=f(n-1,m-v)+w\)说明最后一个物品被选了。

• 也有可能一样，就是最后一个物品选和不选都可以。

• 为了求出字典序最小的，我们逆序推出最优解，输出方案，详见代码。

scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) 
    scanf("%d%d", &v[i], &w[i]);
for(int i = n; i >= 1; i--)
{
    for(int j = 0; j <= m; j++)
    {
        f[i][j] = max(f[i][j], f[i+1][j]);
        if(j >= v[i]) f[i][j] = max(f[i][j], f[i+1][j-v[i]]+w[i]);
    }
}

int cnt = m;
for(int i = 1; i <= n; i++)
{
    if(cnt - v[i] >= 0 && f[i][cnt] == f[i+1][cnt-v[i]]+w[i])
    {
        printf("%d ", i);
        cnt -= v[i];
    }
}

背包九讲学习笔记

原文：https://www.cnblogs.com/zxytxdy/p/12073415.html