wizlyk

wizlyk的代码小天地

0%

Knapsack Problem

发表于 更新于

Knapsack Problem 就是大名鼎鼎的“背包问题”，其中又以“01背包”为大家所熟知。这里记录一下在AcWing上学习的一些背包问题相关的解法。

先来看一段来自维基百科的介绍：
背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。

也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V。

定义

我们有 n 种物品，物品 j 的重量为\(w_j\)，价格为\(p_j\)。 我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。 如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

可以用公式表示为： \[max: \sum_{j = 1}^{n} p_ix_i\] \[ s.t.: \sum_{j=1}^n w_ix_i \leqslant W, x_j \in \{0,1\}\]

如果限定物品 j 最多只能选择 \(b_j\)个，则问题称为有界背包问题

可以用公式表示为： \[max: \sum_{j = 1}^{n} p_ix_i\] \[ s.t.: \sum_{j=1}^n w_ix_i \leqslant W, x_j \in \{0,1,...,b_j\}\]

如果不限定每种物品的数量，则问题称为无界背包问题。

各类复杂的背包问题总可以变化为简单的0-1背包问题进行求解。

计算复杂度

在计算机科学领域，人们对背包问题感兴趣的原因在于：

  • 利用动态规划，背包问题存在一个伪多项式时间算法
  • 把上面算法作为子程序，背包问题存在完全逼近多项式时间方案
  • 作为NP完全问题，背包问题没有一种既准确又快速（多项式时间）的算法

背包问题在我们的生活中是那么的常见（在面试题中也一样），直白的问题和经典的动态规划解法，使得背包问题显得那么重要而基础。

先来看来自于左程云的《程序员代码面试指南》中的例子

1. 换钱的最少货币数 I

给定货币面值，存放于 cash 数组中。求对于指定的钱数 aim， 最少需要几张货币。若不能换，则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
cash = {2,3,5}, aim = 20
Output:
20

Input:
cash = {2,3,5}, aim = 0
Output:
0

Input:
cash = {2}, aim = 1
Output:
-1

由于每个面值的货币都可以使用无数次（即无界背包问题），所以对于每一个面值的货币，我们都可以从最小的钱数开始，每次判断这个数减去面值后所需要的货币数，同时更新该钱数需要的最少货币数。

即转移公式为：

\[ dp[k] = min(dp[k], dp[k-cash[i]]+ 1) \]

如若输入为cash = {2,5}, aim = 6: 最开始时，面值为2的货币，钱为2需要1张，3不行，4需要2张，5不行，6需要3张 然后面值为5的货币，则钱为5需要1张，6需要2张，这个时候就更新6元的货币数，从3改为2。

代码：

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

int minCash(const vector<int> &cash, int aim) {
  vector<int> dp(aim + 1, -1);  // 用于记录最小钱数的数组，是动态规划的基础结构
  dp[0] = 0;
  int n = cash.size();
  for (int i = 0; i < n; ++i) { // 对于第i种货币
    for (int sum = cash[i]; sum <= aim; ++sum) {
      int last = sum - cash[i];
      if (dp[last] == 0) {  // last == 0 的情况
        dp[sum] = 1;
      }
      else if (dp[last] == -1)  // 不能从前一个数中到达sum
        continue;
      else {
        // 判断是否需要更新
        dp[sum] = (dp[sum] == -1 ? dp[last] + 1 : min(dp[sum], dp[last] + 1));
      }
    }
  }
  return dp[aim];
}

上面的例题是货币可以无限取，当只能有限取（即有界背包问题）时，又改怎么变化呢？

再来个例子：

2. 换钱的最少货币数 II

给定你现在有限的钱数，存放于 cash 数组中。求对于指定的钱数 aim， 最少需要几张货币。若不能换（或钱不够），则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
cash = {2,3,5}, aim = 20
Output:
-1

Input:
cash = {5,2,3,5}, aim = 10
Output:
2

Input:
cash = {2}, aim = 0
Output:
0

其实解答的思路和上个例子一模一样，也是用一个数组来存放已经计算好的最少需要的货币数。唯一的不同在于，我们的钱只能用一次，很现实。

注意在上一个例子中，我们重复使用钱的关键在于这一句:

1
for (int sum = cash[i]; sum <= aim; ++sum)

即我们是从小加到大，从而保证了使用某货币c时，大的钱数sum可以由小的钱数sum-c那跳转，而sum-c我们已经计算过了，所以大的钱数sum可以重复使用该货币。

那么如果要让钱不能重复使用，我们就从大往小算就行了，这样，每次计算，前面的最小货币数必定是没有使用当前货币的情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minCash(const vector<int> &cash, int aim) {
  vector<int> dp(aim + 1, -1);
  dp[0] = 0;
  int n = cash.size();
  for (int i = 0; i < n; ++i) {
    for (int sum = aim; sum >= cash[i]; --sum){  // 从大到小算
      int last = sum - cash[i];
      if (dp[last] == 0) {
        dp[sum] = 1;
      }
      else if (dp[last] == -1)
        continue;
      else {
        dp[sum] = (dp[sum] == -1 ? dp[last] + 1 : min(dp[sum], dp[last] + 1));
      }
    }
  }
  return dp[aim];
}

看，其实差距只有一行。

3. 换钱的方法数

假定你现在有面值不同的货币，存放在 cash 数组中，每种货币可以用无数次。求对于一个给定的钱数 aim ，有多少中换钱的方法。

1
2
3
4
5
6
7
8
9
Input:
cash = {1,10,25,5}, aim = 15
Output:
6

Input:
cash = {5,2,3,5}, aim = 1
Output:
0

题目和第一个例子很相似，不同之处在于求解的目标不一样，所以我们动态规划使用的 dp 数组的含义也不一样。

对于例子“换钱的最少货币数 I”， dp 数组的含义是当前状态下，每个数需要的最少货币数； 对于例子“换钱的方法数”， dp 数组的含义是当前状态下，每个数对应的换钱方法数。

转移公式：

\[dp[k] = dp[k]+dp[k-cach[i]]\]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countChanges(const vector<int> &cash, int aim) {
  vector<int> dp(aim + 1, 0);
  dp[0] = -1;  // 0 之所以特殊，是因为任何面值都可以从0开始计算
  int n = cash.size();
  for (int i = 0; i < n; ++i) {
    for (int sum = cash[i]; sum <= aim; ++sum) {
      int last = sum - cash[i];
      if (dp[last] == -1)  // 即 ++dp[cash[i]] 
        dp[sum]++;  
      else if (dp[last] == 0)  // 换不了，那可咋办嘛？答，continue
        continue;
      else 
        dp[sum] += dp[last];  // 加上前面那个数能换的方法数
    }
  }
  return dp[aim];
}

可以看到这里的转移公式和经典的爬梯子问题很像。

讲的很浅，以后有机会再补充例子。

最后再用一道实际的腾讯笔试题来结尾吧。

数字拼凑 小Q有一个长度为n的序列S，序列中有n个正整数。小Q现在和你玩数字游戏，每次小Q说出一个正整数X，你需要从序列中挑选出若干个数字出来进行相加，使结果等于X，如果你不能完成拼凑你就输了。

小Q现在想知道能让你输掉游戏的最小的正整数X是多少？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入描述：
输入包括两行
第一行为一个正整数n，表示序列的长度 1 <= n <= 20
第二行包括n个正整数a[i]，用空格隔开， 1 <= a[i] < 10^5

输出描述：
一个正整数，表示最小的正整数X

示例1：
输入：
3
2 1 4
输出：
8