动态规划：双核CPU调度背后的背包问题

[xxleyi]

题目的大概意思：一种双核 CPU 能够并行处理任务，现在有 n 个已知数据量的任务需要交给 CPU 处理，假设已知 CPU 的每个核 1 秒可以处理 1kb，每个核同时只能处理一项任务。n 个任务可以按照任意顺序放入 CPU 进行处理，现在需要设计一个方案让 CPU 处理完这批任务所需的时间最少，求这个最小的时间。 

输入包括两行：

• 第一行为整数 n(1 ≤ n ≤ 50)
• 第二行为 n 个整数 length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为 1024 的倍数。

输出一个整数，表示最少需要处理的时间。

---

熟悉背包问题之后，发现上述问题就是背包问题的变形，其实质是背包容量为任务总量的一半，如何向背包中放入最多的的任务量。因为任务的颗粒度大小不一，很可能的结果是背包无法被放满。所以处理完这批任务的最小时间为总时间减去背包时间。

---

下面直接针对背包问题求解。

def knapsack(n, capacity, weight, value):
    if not n or capacity == 0:
        return 0
    if weight[n - 1] > capacity:
        return knapsack(n - 1, capacity, weight, value)
    sum_a = knapsack(n - 1, capacity, weight, value)
    sum_b = value[n - 1] + knapsack(n - 1, capacity - weight[n - 1], weight, value)
    return sum_a if sum_a > sum_b else sum_b


weight = [1, 15, 20, 2, 4, 6, 5, 8]
value = [2, 2, 4, 1, 1, 3, 1, 1]
capacity = 20
n = len(weight)
knapsack(n, capacity, weight, value)

这个是貌似简明的递归方案。在背包问题中的递归中，递归基比较简单，就是如果物件数量为零或背包容量为零的话，所能放下的东西为零。有了递归基还不够，还需要找出另外一种确定性：状态之间的递归关系。

递归就是倒推，此处倒推有三种情况：

• W(n) > C，f(n, C, W, V) = f(n-1, C, W, V)
• W(n) <= C，f(n, C, W, V) = max(f(n-1, C, W, V), V[n] + f(n-1, C-W[n], W, V))

结合这些具有确定性的关系以及递归基，我们直接完成信念的飞跃，认为我们已然成功解决问题。

---

递归之后还可以通过 memoizatation 优化计算复杂度，并进一步强迫自己观察具体的计算过程。

cache = {}

def knapsack(n, capacity, weight, value):
    if (n, capacity) in cache:
        return cache[(n, capacity)]

    if not n or capacity == 0:
        res = 0
    elif weight[n - 1] > capacity:
        res = knapsack(n - 1, capacity, weight, value)
    else:
        sum_a = knapsack(n - 1, capacity, weight, value)
        sum_b = value[n - 1] + knapsack(n - 1, capacity - weight[n - 1], weight, value)
        res = sum_a if sum_a > sum_b else sum_b

    cache[(n, capacity)] = res

    return res


weight = [1, 15, 20, 2, 4, 6, 5, 8]
value = [2, 2, 4, 1, 1, 3, 1, 1]
capacity = 20
n = len(weight)
knapsack(n, capacity, weight, value)
import pprint
pprint.pprint(cache)

cache:

{(0, 0): 0,
 (0, 1): 0,
 (0, 2): 0,
 (0, 3): 0,
 (0, 4): 0,
 (0, 5): 0,
 (0, 6): 0,
 (0, 7): 0,
 (0, 8): 0,
 (0, 9): 0,
 (0, 10): 0,
 (0, 11): 0,
 (0, 12): 0,
 (0, 13): 0,
 (0, 14): 0,
 (0, 15): 0,
 (0, 16): 0,
 (0, 17): 0,
 (0, 18): 0,
 (0, 19): 0,
 (0, 20): 0,
 (1, 0): 0,
 (1, 1): 2,
 (1, 2): 2,
 (1, 3): 2,
 (1, 4): 2,
 (1, 5): 2,
 (1, 6): 2,
 (1, 7): 2,
 (1, 8): 2,
 (1, 9): 2,
 (1, 10): 2,
 (1, 11): 2,
 (1, 12): 2,
 (1, 13): 2,
 (1, 14): 2,
 (1, 15): 2,
 (1, 16): 2,
 (1, 18): 2,
 (1, 20): 2,
 (2, 0): 0,
 (2, 1): 2,
 (2, 2): 2,
 (2, 3): 2,
 (2, 4): 2,
 (2, 5): 2,
 (2, 6): 2,
 (2, 7): 2,
 (2, 8): 2,
 (2, 9): 2,
 (2, 10): 2,
 (2, 11): 2,
 (2, 12): 2,
 (2, 13): 2,
 (2, 14): 2,
 (2, 15): 2,
 (2, 16): 4,
 (2, 18): 4,
 (2, 20): 4,
 (3, 0): 0,
 (3, 1): 2,
 (3, 2): 2,
 (3, 3): 2,
 (3, 4): 2,
 (3, 5): 2,
 (3, 6): 2,
 (3, 7): 2,
 (3, 8): 2,
 (3, 9): 2,
 (3, 10): 2,
 (3, 11): 2,
 (3, 12): 2,
 (3, 13): 2,
 (3, 14): 2,
 (3, 15): 2,
 (3, 16): 4,
 (3, 18): 4,
 (3, 20): 4,
 (4, 1): 2,
 (4, 2): 2,
 (4, 3): 3,
 (4, 5): 3,
 (4, 6): 3,
 (4, 7): 3,
 (4, 8): 3,
 (4, 9): 3,
 (4, 10): 3,
 (4, 11): 3,
 (4, 12): 3,
 (4, 14): 3,
 (4, 15): 3,
 (4, 16): 4,
 (4, 20): 5,
 (5, 1): 2,
 (5, 6): 3,
 (5, 7): 4,
 (5, 9): 4,
 (5, 12): 4,
 (5, 14): 4,
 (5, 15): 4,
 (5, 20): 5,
 (6, 7): 5,
 (6, 12): 6,
 (6, 15): 7,
 (6, 20): 7,
 (7, 12): 6,
 (7, 20): 8,
 (8, 20): 8}

进一步把 cache 转化为一个二维表格：

table = [[None] * 21 for _ in range(9)]
for k in cache:
    table[k[0]][k[1]] = cache[k]
for i in table:
    print(i)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, None, 2, None, 2]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, None, 4, None, 4]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, None, 4, None, 4]
[None, 2, 2, 3, None, 3, 3, 3, 3, 3, 3, 3, 3, None, 3, 3, 4, None, None, None, 5]
[None, 2, None, None, None, None, 3, 4, None, 4, None, None, 4, None, 4, 4, None, None, None, None, 5]
[None, None, None, None, None, None, None, 5, None, None, None, None, 6, None, None, 7, None, None, None, None, 7]
[None, None, None, None, None, None, None, None, None, None, None, None, 6, None, None, None, None, None, None, None, 8]
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 8]

把 None 替换为 N，更方便观看：

N = None
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, N, 2, N, 2]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, N, 4, N, 4]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, N, 4, N, 4]
[N, 2, 2, 3, N, 3, 3, 3, 3, 3, 3, 3, 3, N, 3, 3, 4, N, N, N, 5]
[N, 2, N, N, N, N, 3, 4, N, 4, N, N, 4, N, 4, 4, N, N, N, N, 5]
[N, N, N, N, N, N, N, 5, N, N, N, N, 6, N, N, 7, N, N, N, N, 7]
[N, N, N, N, N, N, N, N, N, N, N, N, 6, N, N, N, N, N, N, N, 8]
[N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 8]

[xxleyi]

邓老师名言：递归貌似简明，迭代至拙至巧。

有了逆向的递推方程，还需要再将其转换为正向的状态转移方程。

• f(0, C, W, V) = 0
• f(n, 0, W, V) = 0

这俩初始条件意味着有两个初始值均为 0 的向量。

再加上最终要求解的是 f(N, C, W, V)，N 为物件总数量，所以很明显，迭代过程是在一个二维向量上进行。

具体来说，我们需要一个 (N+1) x (C+1) 的二维向量 K。然后初始情况为任意 K[0][c] 和 任意 K[w][0] 均为零。

进一步分析一下，发现这个初始化的过程其实就是递归版解法的递归基，从而也就是迭代版的行零或列零情况。

接下来直接迭代即可。

def knapsack(N, C, W, V):
    # N+1  rows
    # C+1  columns
    K = [[0] * (C + 1) for _ in range(N + 1)]

    # Num. 1 -> N+1 row
    for n in range(1, N + 1):
        # Num. 1 -> C+1 row
        for c in range(1, C + 1):
            if W[n - 1] > c:
                K[n][c] = K[n - 1][c]
            else:
                K[n][c] = max(K[n - 1][c], V[n - 1] + K[n - 1][c - W[n - 1]])
    for i in K:
        print(i)
    return K[n][c]


# weight list
W = [1, 15, 20, 2, 4, 6, 5, 8]
# value list
V = [2, 2, 4, 1, 1, 3, 1, 1]
# capacity of knapsack
C = 20
# total number of weight list
N = len(W)
max_v = knapsack(N, C, W, V)

K:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4]
[0, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5]
[0, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8]

[xxleyi]

memoizatation vs tabulation

memo:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, N, 2, N, 2]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, N, 4, N, 4]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, N, 4, N, 4]
[N, 2, 2, 3, N, 3, 3, 3, 3, 3, 3, 3, 3, N, 3, 3, 4, N, N, N, 5]
[N, 2, N, N, N, N, 3, 4, N, 4, N, N, 4, N, 4, 4, N, N, N, N, 5]
[N, N, N, N, N, N, N, 5, N, N, N, N, 6, N, N, 7, N, N, N, N, 7]
[N, N, N, N, N, N, N, N, N, N, N, N, 6, N, N, N, N, N, N, N, 8]
[N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, 8]

tabulation:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4]
[0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4]
[0, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5]
[0, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8]
[0, 2, 2, 3, 3, 3, 3, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8]

如此一来，孰快孰慢，还真就不一定了。