未分类

【动态规划】从子集和问题到背包问题

数据结构与算法

一、问题定义

有一个包含n个元素{e1, e2, ..., en}的集合S，每个元素ei都有一个对应的权值wi。现在有一个界限W，我们希望从S中选择出部分元素，使得这些元素的权值之和在不超过W的情况下达到最大，这个便是子集合问题（事实上还有其他类型的子集和问题，本文暂不讨论）。举个更具体一点的例子，某农民今年收成小番茄总重量为W万斤，有n个采购商想要向这位农民收购小番茄，他们想要采购的数目都有所不同，采购商i想要收购wi万斤小番茄(1 <= i <= n)。现在农民需要从采购商中挑选部分买家，将小番茄卖给他们，使得自己被收购的小番茄数目达到最大，从而赚取最大的收入（假设所有采购商给出的单位收购价都是一样的；所有采购商的收购量总和超过农民的收成量，即农民无法满足所有采购商；收购商i想要收购wi万斤小番茄，他不会只收购一半或者更多）。

二、解决思路

根据动态规划的思路，我们来分析一下这个问题的子问题。假设农民已经从前面n-1个收购商中选出了一组最优组合使得收购量最大，现在他要考虑是否要卖给最后一个收购商n。假如卖给收购商n，那么他能够卖给前面n-1个收购商的番茄就只有(W-wn)万斤。如果他不卖给收购商n，那么他能够卖给前面n-1个收购商的番茄就是W万斤了。于是，假设在只有(W-wn)万斤的情况下，从前面n-1个收购商中选出最优组合所收购的总重量加上卖给收购商n的重量为(O1+wn)。若W万斤都卖给前面n-1个收购商，他们之中选出的最优组合所收购的总重量为O2。农民需要考虑的问题就变成了比较(O1+wn)和O2的大小了。

我们更形式化一点地进行描述，假设O(i, w)表示将w万斤小番茄提供给收购商{1, 2, ..., i}收购的时候，从这i个收购商中选出最优组合所收购的总重量。那么O1 = O(n-1, W-wn)，O2 = (n-1, W)。当农民考虑收购商n的时候，他需要判定O1和O2的大小。另外一种特殊情况，当收购商收购的数量wn超过农民拥有的所有小番茄的时候，即W < wn，那么农民自然只能考虑前面n-1个收购商中的最优组合了。

更进一步考虑，当我们考虑O(i, w)的时候，如果w能够容纳wi，那么我们需要考虑O(i-1, w)和(O(i-1, w-wi) + wi)的大小。如果w无法容纳wi，即w < wi，那么无需考虑i，O(i, w) = O(i-1, w)。因此，我们可以得到递推公式如下所示：

1
2
if w < wi, O(i, w) = O(i-1, w)
else O(i, w) = max(O(i-1, w), wi + O(i-1, w-wi))

得到了递推公式，我们自然就可以得到一个算法来算出最优解。算法的伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
数组O[0...n, 0...W]
for w = 0, 1, ..., W
    初始化O[0, w] = 0
endFor
for i = 1, 2, ..., n
    for w = 0, ..., W
        if w < wi
            O[i, w] = O[i-1, w]
        else
            O[i, w] = max(O[i-1, w], wi + O[i-1, w-wi])
    endFor
endFor
O[n, W]即为最优解

算法实际上是实现了一个填表的过程，填了一张n*W的二维表格。整个算法的时间复杂度为O(nW)，显而易见，当W的值变得很大的时候，这个算法的效率堪忧。

二维表格

现在暂时抛开效率问题，我们发现，上面给出的算法只能算出最优解的值，但是并没有给出所选择的子集合。即农民用这个算法之后只知道他最多能卖多少小番茄，但还是不知道要卖给哪些收购商。为了解决这个问题，我们只需要反向搜索一下数组O即可在O(n)的时间内找出最优解的元素组合情况。反向搜索的时候，如果O(i, w)等于O(i-1, w)，说明i没有被选择，继续对前面i-1个元素考虑重量为w时候的情况。如果O(i, w)不等于O(i-1, w)的话，说明选择了i，然后接着就应该继续对前面i-1个元素考虑重量为(w-wi)时候的情况，具体的伪代码如下所示：

1
2
3
4
5
6
7
8
9
10
初始化i = n, w = W
while i != 0 do
    if O[i, w] == O[i-1, w]
        i = i-1
    else
        print i
        i = i-1
        w = w-wi
    endIf
endWhile

三、代码实例

下面给出一个简单的C++代码实现，代码后面还附带有简单的示例。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
using namespace std;

const int MAX_NUM = 100;
const int MAX_WEIGHT = 1000;

class SubSetProblem {
public:
  void init(int n, int W) {
    this->n = n;
    this->W = W;
    memset(optional, 0, sizeof(optional));
    for (int i = 1; i <= n; ++i) {
      cin >> weight[i];
    }
  }
  void process() {
    for (int i = 1; i <= n; ++i) {
      for (int w = 0; w <= W; ++w) {
        if (w < weight[i]) {
          optional[i][w] = optional[i-1][w];
        } else if (optional[i-1][w] < weight[i] + optional[i-1][w-weight[i]]) {
          optional[i][w] = weight[i] + optional[i-1][w-weight[i]];
        } else {
          optional[i][w] = optional[i-1][w];
        }
      }
    }
  }
  void result() {
    cout << "[Select]";
    for (int i = n, w = W; i != 0; --i) {
      if (optional[i][w] == optional[i-1][w]) {
        continue;
      } else {
        cout << ' ' << i;
        w -= weight[i];
      }
    }
    cout << "\n[Optional] " << optional[n][W] << endl;
  }
private:
  int n, W;
  int weight[MAX_NUM + 1];
  int optional[MAX_NUM + 1][MAX_WEIGHT + 1];
};

int main() {
  SubSetProblem ssp;
  int n, W;
  cin >> n >> W;
  if (n > MAX_NUM || W > MAX_WEIGHT) {
    cout << "error" << endl;
    return -1;
  }
  ssp.init(n, W);
  ssp.process();
  ssp.result();
  return 0;
}

输入输出示例：

1
2
3
4
3 6
2 2 3
[Select] 3 1
[Optional] 5

四、背包问题

把上面的子集和问题拓展一下，就变成了我们常见的背包问题了。问题定义：有一个包含n个元素{e1, e2, ..., en}的集合S，每个元素ei都有一个对应的权值wi和一个对应的价值vi。现在有一个界限W，我们希望从S中选择出部分元素，使得这些元素的权值之和在不超过W的情况下，所有元素的价值总和达到最大。继续拿上面的农民买小番茄的例子来讲，假设现在每个收购商的出价都有所不同，收购商i打算收购wi万斤小番茄，出价vi。农民只有W万斤能够提供给收购商，他希望合理选择收购商，使得卖小番茄的收益达到最大。

这个问题看起来跟前面的子集和问题很像，解决思路也是基本一样。同样地，农民在考虑收购商n的时候，他需要考虑两个子问题。第一，如果把W万斤小番茄全部拿来提供给前面的n-1个收购商，他能拿到的最大收益为O(n-1, W)。第二，如果先出售部分小番茄给收购商n，剩下的再提供给前面n-1个收购商，他能拿到的最大收益为(O(n-1, W-wn) + vn)。于是，只要O(n-1, W)的价值更大，农民自然不会考虑收购商n，否则他肯定要先出售部分小番茄给收购商n。最后，考虑特殊情况，当收购商n的收购量超过农民所能提供的小番茄时，农民也就只能将W万斤小番茄提供给前面n-1个收购商了。

假设O(i, w)表示农民将w万斤小番茄提供给前i个收购商所能赚取的最大收益，按照之前讲解子集和问题的思路，我们可以得到递推公式如下：

1
2
if w < wi, O(i, w) = O(i-1, w)
else O(i, w) = max(O(i-1, w), vi + O(i-1, w-wi))

可以看到，公式几乎跟之前的子集和问题一样。只不过，子集和问题中我们考虑的是重量w，而这里我们考虑的是价值v。两者本质上是同样的，只不过判定的标准变了而已。解决这种类型的背包问题的算法跟之前的一样，只需要将wi换成vi即可，最后反向搜索求解最优解的元素组合情况的做法也是与之前一样，代码相似度较高，所以下面我就不重复贴代码了。这个算法的时间复杂度也是O(nW)，反向搜索的时间复杂度为O(n)。算法缺陷也是跟之前一样，当W的值非常大的时候，算法效率低下。

分享到