3.2 金矿问题

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

有一个国家，所有的国民都非常老实憨厚，某天他们在自己的国家发现了 \(n\) 座金矿，国王知道这个消息后非常高兴，他希望能够把这些金子都挖出来造福国民。后他找到了这个领域的专家小八，对每一座金矿进行勘测，勘测发现挖掘每个金矿所需的人数是固定的（一个也不需要多，一个也不能少），而且这些金矿也有主矿和副矿的区别，主矿可以直接进行挖掘，但是副矿必须在挖掘完其对应的主矿后才能进行挖掘，否则会有相当的风险。每个主矿可能有 0 个、1 个或 2 个副矿，每个副矿都只对应 1 个主矿，且副矿不会再有副矿。了解完这些后，国王决定派 \(v\) 个矿工去挖金矿。（\(v\) 个矿工不一定要全部用完）

现给出金矿数量 \(n\) 及矿工数量 \(v\) ，以及每个金矿的具体情况。求最多能获得的金子数量。

数据输入

第 1 行为两个正整数\(v\ n\)，其中 \(v\ (2\leq v\leq 100)\)，表示所有矿工数量，\(n\ (2\leq n\leq 1000)\)，为金矿的数量。

接下来的\(n\) 行，第 \(i\) 行给出了编号为 \(i\) 的金矿的基本数据，每行有 3 个非负整数\(V_i\ W_i\ M_i\)。其中 \(V_i\) 表示挖掘该金矿所需的矿工数目，\(W_i\) 表示该金矿的含金量，\(M_i\) 表示该金矿是主矿还是副矿。如果 \(M_i=0\)，表示该金矿是主矿，如果 \(M_i>0\)，表示该金矿为副矿，\(M_i\)是所属主矿的编号。

数据输出

输出只有一行，表示最多的金子数量。

输入示例 输出示例
100 5
80 100 0
40 500 1
20 300 1
20 100 0
50 200 0		 400

源代码（转化为分组背包）

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
#include <stdio.h>
#include <string.h>
const int maxv = 107;
const int maxn = 1007;
inline int max(int a, int b){ return a < b ? b : a; }
int dp[maxv];

struct Goldmine {
    int v, w, m, cnt, sub[2];
    void in() { scanf("%d%d%d", &v, &w, &m); }
    void addSub(int x) { sub[cnt++] = x; }
    Goldmine() :cnt(0){}
} gm[maxn];

//依赖背包
int main() {
    int v, n, i, j, k, h;
    bool flag = 1;
    scanf("%d%d", &v, &n);
    for (i = 1; i <= n; ++i) {
        gm[i].in();
        if (gm[i].m > 0) gm[gm[i].m].addSub(i);
    }
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= n; ++i) if (gm[i].m == 0) {//其实是转化为分组背包求解
        for (j = v; j > 0; --j) {//dp[i][j]=max(dp[i-1][j],dp[i-1][j-V_k]+W_k)
            for (k = 0; k < (1 << gm[i].cnt); ++k)//dp组内每一个方案
            {//如果依赖数比较大可以先对所有分组进行一次01背包的预dp
                int V = gm[i].v, W = gm[i].w;
                for (h = 0; h<gm[i].cnt; ++h) if (k >> h & 1) {
                    V += gm[gm[i].sub[h]].v;
                    W += gm[gm[i].sub[h]].w;
                }//由于没有预dp，可能存在不合法的组合
                if (V <= j) dp[j] = max(dp[j], dp[j - V] + W);
            }
        }
    }
    printf("%d\n", dp[v]);
    return 0;
}

设计思路与复杂度分析

此题为依赖背包问题，具体请参考背包九讲第 6-7 讲。做法是将依赖背包问题转化为分组背包问题求解。此时每一个分组包含\(2^{cnt}\)个“物品”（\(cnt\) 为附件个数），\(cnt\)比较小时可以直接枚举。复杂度为\(O(\sum _{i=1}^n v \times 2^{cnt_i} \times cnt_i)\)（\(n\) 为分组数量）。但是当某一个\(cnt_i\)比较大时自然会超时，所以需要寻找一个优化策略，让算法复杂度上界不受\(cnt_i\) 的影响。

其实当\(2^{cnt_i} \times cnt_i>v\)时（本题为\(cnt \geq 5\)）可以对该分组的“附件集合”先进行一次01背包的\(dp\)。因为要考虑附件的前提是主件必须选取，所以该\(vector\) 大小为背包总容量减去主件的大小（最多可以有这么多容量分配给该分组的附件）。这样做的目的是可以排除许多容量大于可用容量的组合，从而加速算法过程。有了这个\(dp\) 过程，代码第34行就可以不用判断了。该预处理的时间复杂度为\(O(k \times cnt_i\times v)\)（\(k\)为需要预处理的分组数量）。将无需预处理的分组中\(2^{cnt_i}\)放大到\(v\)，则优化后的算法时间复杂度为\(O(n \times v^2)\)。

当然，以上代码是一个通用解法，针对本题这样做并不是最优的解法。该算法中每一个分组会枚举很多次，由于没有预处理，所以每一次枚举都会有时间消耗。如果使用一个滚动数组\(dp\)，可以将时间复杂度优化到\(O(\sum _{i=1}^n v \times 2^{cnt_i})\)。现给出代码供参考。

源代码（滚动数组）

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
#include <stdio.h>
#include <string.h>
const int maxv = 107;
const int maxn = 1007;
inline int max(int a, int b){ return a < b ? b : a; }
int dp[2][maxv];

struct Goldmine {
    int v, w, q, cnt, sub[2];
    void in() { scanf("%d%d%d", &v, &w, &q); }
    void addSub(int x) { sub[cnt++] = x; }
    Goldmine() :cnt(0){}
} gm[maxn];

int main() {
    int v, n, i, j, k;
    bool flag = 1;
    scanf("%d%d", &v, &n);
    for (i = 1; i <= n; ++i) {
        gm[i].in();
        if (gm[i].q > 0) gm[gm[i].q].addSub(i);
    }
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= n; ++i) if (gm[i].q == 0) {
        //dp[i][j]=max(dp[i-1][j],dp[i-1][j-V_k]+W_k)
        //其实不是严格意义上的滚动数组，由于每一个组合都会依赖于dp[i-1] 所以需要备份
        memcpy(dp[!flag], dp[flag], sizeof(dp) >> 1);
        for (k = 0; k<1 << gm[i].cnt; ++k) {//交换内外层循环
            int V = gm[i].v, W = gm[i].w;
            for (j = 0; j<gm[i].cnt; ++j) if (k >> j & 1) {
                V += gm[gm[i].sub[j]].v;
                W += gm[gm[i].sub[j]].w;
            }
            for (j = V; j <= v; ++j)
                dp[flag][j] = max(dp[flag][j], dp[!flag][j - V] + W);
        }
    }
    printf("%d\n", dp[flag][v]);
    return 0;
}
0%