递归的几个应用

一、引入

通过最大子段和、简单装载问题、0/1背包问题这三个问题，加深对递归应用的理解。

二、最大子段和

给出一段序列，求这个序列的最大子段和。

比如-2,11,-4,13,-5,-2 最大的子段和就是11,-4,13这个序列的和，是20；

我们采用分治的思想来解决这个问题。

如果将一个序列分成两部分，那么这个序列的最大子序列所在位置有三种情况：

1.在左侧序列中。

2.在右侧序列中。

3.横跨两个序列，一部分在左侧序列，一部分在右侧序列。

根据这三种情况，我们可以求得左侧序列最大的和，右侧序列最大的和，以及横跨两部分的最大的和，在比较这三者便可以得出最大的和。

对于左侧或者右侧序列的最大的和，我们可以再将他分为两部分，再去求，即，分治的思想。

对于横跨两部分的最大的和，我们可以从中间分别向两边累加求和，取和的最大值即可。

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
int maxsubsum(int l, int r)
{
    if (l == r)
        return nums[l];
    int mid = (l + r) / 2;
    int lsum = maxsubsum(l, mid); // 左侧最大和
    int rsum = maxsubsum(mid + 1, r); // 右侧最大和

    int s1 = nums[mid], s2 = nums[mid + 1];
    int sum = 0;

    // 横跨两部分的和
    for (int i = mid; i >= l; i--) // 从中间到左边界这部分最大的和
    {
        sum += nums[i];
        s1 = max(s1, sum);
    }

    sum = 0;

    for (int i = mid + 1; i <= r; i++) // 从中间到右边界这部分最大的和
    {
        sum += nums[i];
        s2 = max(s2, sum);
    }
    
    // s1 + s2 即横跨两部分的最大的和
    return max(s1 + s2, max(lsum, rsum)); // 三部分中最大的和
}

时间复杂度为O(nlogn)

三、简单装载问题

题目：

有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要这些集装箱中选出若干装上轮船，使它们的重量之和等于W，当总重量相同时要求选取的集装箱个数尽可能少。

可以遍历这些集装箱，对于集装箱i，有两种处理情况，分别是选和不选。这样就会得到一个二叉树的解结构。

在递归求解的过程中可以剪枝，比如，如果当前集装箱不选，剩下的集装箱重量和不足W，那么这个集装箱是必须要选的。如果选择当前的集装箱，重量超过了W，那么这个集装箱是一定不可以选的。

举一个例子，五个集装箱，重量分别为5,2,6,4,3，要求中重量达到10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int num, int tw, int rw, int op[], int i) // num代表已经选择的集装箱个数，tw已选总总量，rw剩余重量，i考虑第i个集装箱
{
    if (tw == W) // 重量符合
    {
        if (num < minnum) // 同时数量还是更少的，那么就存入答案
        {
            for (int j = 0; j < MAXN; j++)
                x[j] = op[j];
            minnum = num;
        }
        return;
    }

    if (tw + w[i] <= W && i < n) // 选择的情况
    {
        op[i] = 1;
        dfs(num + 1, tw + w[i], rw - w[i], op, i + 1);
        op[i] = 0; // 递归结束，要将其设置为没选
    }
    if (tw + rw - w[i] >= W && i < n) // 不选择的情况
        dfs(num, tw, rw, op, i + 1);
}

四、01背包问题

给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求而且重量和恰好为W具有最大的价值。这个与上面的简单装载问题差不多，只不过是条件变了变，也是逐一考虑每个物品，有两种情况，选择与不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int i, int tw, int tv, int rw, int op[]) // i考虑第i个物品，tw当前重量，tv当前价值，rw背包剩下的空间
{
    if (tw == W && tv > maxv) // 重量恰好为W时，并且价值更高则修改答案。
    {
        for (int j = 0; j < n; j++)
            x[j] = op[j];
        maxv = tv;
    }

    if (tw + w[i] <= W && i < n) // 能装得下，继续装
    {
        op[i] = 1;
        dfs(i + 1, tw + w[i], tv + v[i], rw - w[i], op);
        op[i] = 0; // 递归结束，要将其设置为没选
    }
    if (i < n) // 不选择
        dfs(i + 1, tw, tv, rw, op);
}