Knapsack Problem

Posted on Edited on In
背包问题

01背包

从搜索说起

简化问题

考虑这样一个问题：有一个背包和有个物品，单价为（可负），求装进背包的最大价值

  • 递归的重复逻辑：对于任一物品，有选与不选两种情况；而解是这两种情况中的大者
  • 递归的边界：没有更多物品了
1
2
3
4
5
int Dfs(const int &x) { // 第 x 个物品
  if (x == 0) return 0;  // x = 0 不是物品
  return std::max(Dfs(x - 1), Dfs(x - 1) + v[i]); // 选与不选的大者为解
}
// Call: Dfs(N);

暴力01背包

再把这个问题升级，加入一个限制条件：背包最大负重为，以及每个物品都有一定重量
也就是说：有一个最大负重为的背包，和个物品，单重为、单价为，求装进背包的最大价值

  • 加入这个限制条件后，递归函数需要一个额外的参数：剩余的背包负重，以判断是否放得下这个物品
1
2
3
4
5
6
int Dfs(const int &x, const int &y) { // 剩余的背包负重为 y
  if (x == 0) return 0;
  if (y < w[x]) return Dfs(x - 1, y); // 放不下了，看看下一个
  return std::max(Dfs(x - 1, y), Dfs(x - 1, y - w[x]) + w[x]);
}
// call: Dfs(N, Wmax)

这样就可以解01背包了，但是，算法的时间复杂度是（深度为n的二叉树），难以接受

优化：记忆化+贪心

  • 深度为n的二叉树中，可以用一个3元组记录每个节点：(x, y, res)，其中x, y意义与Dfs(x, y)相同，决定了以此节点为根的子树的结构；res则为其解。
  • 利用贪心可以进行剪枝：若有3元组t1, t2，且t1.x = t2.x, t1.x = t2.y，则它们的子树结构相同。而此时抛弃res小的节点而选择大者是不会影响根节点的结果值的。
  • 故可以用一个二维数组dp[x][y] = res记录节点(x, y, res)，并维护res最大
1
2
3
4
5
6
7
8
// memset(dp, 0xff, sizeof(dp));
int Dfs(const int &x, const int &y) { // 剩余的背包负重为 y
  if (dp[x][y] >= 0) return dp[x][y];
  if (x == 0) return dp[x][y] = 0;
  if (y < w[x]) return dp[x][y] = Dfs(x - 1, y); // 放不下了，看看下一个
  return dp[x][y] = std::max(Dfs(x - 1, y), Dfs(x - 1, y - w[x]) + w[x]);
}
// call: Dfs(N, Wmax)

时间复杂度是（对于每个x, y，dp[x][y]只会进入递归一次（当其值为初始时））

动态规划的01背包

经过优化后的算法，其解不再是一颗二叉树了，剪枝之后成为一个表；而用循环的写法更加简单直观，可以改写成以下的形式：

1
2
3
4
5
6
7
8
9
10
11
12
// const int kInf = -0x3f3f3f3f;
int SolveZeroOneKnapsack() {
  for (int i = 0; i <= Wmax; ++i) dp[0][i] = -kInf;
  for (int i = 1; i <= N; ++i)
    for (int j = 0; j <= Wmax; ++j)
      if (j < w[i]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - w[i]] + w[i]); 
      }
  return dp[N][Wmax];
}

这就是所谓的动态规划了，其与递归的不同也可以直观的看出来：递归是从大到小的，而动态规划是从小到大的（递归在填表时也是从小到大的）。

被称作状态转移方程，负责从小推大

小的状态有二：其中对应不选第件，对应选的情况

记忆化+贪心与动态规划的关系

能采用动态规划解决的问题，一般要具有三个性质：来源

  1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
  2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
  3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

分析01背包的记忆化搜索+贪心算法与以上3点的关系，可以发现：

  1. 最优化原理由贪心满足了
  2. 搜索过程中的类似后续遍历的顺序，决定了状态x-1在状态x之前确定，并不再改变，即满足无后效性
  3. 显然

压缩数组

分析状态转移方程，发现：

  • 状态仅由转移得来
  • 故处于状态时，可以省去，从而降低空间复杂度
  • 使用二维数组实现时，的顺序无关紧要
  • 使用一维数组实现时，的顺序变得重要了：省去的是，故应倒序
1
2
3
4
5
6
7
// Init
for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

// DP
for (int i = 1; i <= N; ++i)
  for (int j = Wmax; j >= w[i]; --j)
    dp[j] = Max(dp[j], dp[j - w[i]] + v[i]);

满载限制

添加一个限制条件：只有装满背包的方案才是合法的，装不满输出-1

解法是：初始化时dp[i] = -kInf, dp[0] = 0，这样，最终DP完成后判断dp[Wmax] < 0即可

完全背包

有一个最大负重为的背包，和种物品，每种无限个，单重为、单价为，求装进背包的最大价值

有状态转移方程：

其中对应不选第件，对应选的情况

因为每种无限个的条件，又有由当前种类的选择转移而来，故应是而非

与01背包相同，仍可进行空间压缩，此时省去的是，故应正序

1
2
3
4
5
6
7
// Init
for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

// DP
for (int i = 1; i <= N; ++i)
  for (int j = w[i]; j <= Wmax ++j)
    dp[j] = Max(dp[j], dp[j - w[i]] + v[i]);

多重背包

有一个最大负重为的背包，和种物品，每种个数为、单重为、单价为，求装进背包的最大价值

朴素算法

对01背包的原理略有理解之后，可以这样写：变为共有个物品的01背包：

1
2
3
4
5
6
7
// Init
for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

// DP
for (int i = 1; i <= N; ++i)
  for (int j = 1; j <= C[i]; ++j)
    for (int k = Wmax; k >= W[i]; --k) dp[k] = Max(dp[k], dp[k - W[i]] + V[i]);

也可以这样理解：对于每种物品，枚举选取几个，视作单价=单价×个数，重量=重量x个数的单个物品，即变成01背包问题：

1
2
3
4
5
6
7
8
9
// Init
for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

// DP
for (int i = 1; i <= N; ++i)
  for (int j = 1; j <= C[i]; ++j) {
    int w = j * W[i], v = j * V[i];
    for (int k = Wmax; k >= w; --k) dp[k] = Max(dp[k], dp[k - w] + v);
  }

以上两种的时间复杂度，都为，第二种常数略低一点

二进制优化

当增大时，上面的算法时间复杂度可能会很高，有没有什么优化空间？

对于第一种做法：选取了第一种的第一件与第二件，与选取了第一种的第二件和第三件，这两种状态是相同的

例如：对于
选个：
选个：
选个：

对于第二种做法：当依次选取、个、和个时，若有，显然在完成的基础上选取时，会经过状态即，那么状态被访问了不止一次，这就是可优化之处

例如：对于
选个：
选个：
选个：

想要优化，就要让每个状态被访问的次数尽可能的少，考虑第二种做法，有没有办法让每个，被唯一的一对表示呢？答案就是二进制：

对于任意，有，也就是说只能被每个相加至多次得到

那么考虑的情况：将拆分成件，就能让每个状态只被访问一次了

而不是的整数次幂时怎么办？在末尾加上非整数部分即可（注意一定要末尾，否则会导致某些状态被重复访问）

时间复杂度，

模板

模板题：洛谷P1776 宝物筛选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

const int kN = 1e5 + 1;
int N, Wmax, V[kN], W[kN], C[kN];
int dp[kN];

inline size_t HighBit(size_t x) {
  for (size_t i = 1; i < sizeof(x) << 3; i <<= 1) x |= (x >> i);
  return (x >> 1) + 1;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0), std::cout.tie(0);

  std::cin >> N >> Wmax;
  for (int i = 1; i <= N; ++i) std::cin >> V[i] >> W[i] >> C[i];
  for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

  for (int i = 1; i <= N; ++i) {
    int hb = HighBit(C[i] + 1);
    int remainder = C[i] + 1 - hb;
    for (int j = 1; j < hb; j <<= 1) {
      int w = j * W[i], v = j * V[i];
      for (int k = Wmax; k >= w; --k) dp[k] = std::max(dp[k], dp[k - w] + v);
    }
    if (remainder) {
      int w = remainder * W[i], v = remainder * V[i];
      for (int k = Wmax; k >= w; --k) dp[k] = std::max(dp[k], dp[k - w] + v);
    }
  }

  std::cout << dp[Wmax] << "\n";
  return 0;
}

为了实现了这样的效果：
14 = 7 + (7)
15 = 15 + (0)
16 = 15 + (1)
17 = 15 + (2)
使用HighBit(x)函数取出x的二进制最高位，其原理是：将最高位1扩散到低位，之后右移1位再加1进位即可

分组背包

有一个最大负重为的背包，和件物品，单重为、单价为；同时这些物品被划分为多组，同组的最多选一个，求装进背包的最大价值

就是变成了将组视作01背包中的个，同时这些个的重量和价值不一定相等

模板题：洛谷P1757 通天之分组背包

1
2
3
4
5
6
for (int i = 0; i <= Wmax; ++i) dp[i] = 0;

for (const auto &i : G) // G是组的集合，i是一个组
  for (int j = Wmax; j >= 0; --j)
    for (const auto &k : i) // i是一个组，k是组中物品的索引
      if (j >= W[k]) dp[j] = Max(dp[j], dp[j - W[k]] + V[k]);

贪心优化

显然，对于同组的物品：

  • 当重量相同时，选择价值最大的总是最好的
  • 当价值相同时，选择重量最小的总是最好的