动态规划:特朗普怎样才能赢?

美国大选正在如火如荼进行当中,假如你是特朗普的竞选助手,大选前要去各州开展竞选宣传活动,但是现在你只有10天时间,没有办法每个州都去,需要根据各州的重要性和时间花费拿出一套方案,否则就将被特朗普fire掉。

动态规划:特朗普怎样才能赢?

假设每个州初始情况都是中立的,只要去开展宣传活动就能获得选票,每个州的选举人票数是不一样的,但是票数越多的州需要花费的时间也越多,在时间有限的情况下,你该怎么安排行程,让竞选的胜算更大呢?

下面是每个州的选举人票数:

动态规划:特朗普怎样才能赢?

为了把问题简化,我们这里只考虑取选票数前10的州,time字段表示去这个州宣传活动所需的时间,单位是天:

all_states = [
    {'name':'加利福尼亚州''votes':55'time':5},
    {'name':'德克萨斯州''votes':38'time':3},
    {'name':'佛罗里达州''votes':29,'time':2},
    {'name':'纽约州''votes':29'time':2},
    {'name':'伊利诺伊州''votes':20'time':1},
    {'name':'宾西法利亚州''votes':20,'time':1},
    {'name':'俄亥俄州','votes':18,'time':1},
    {'name':'密歇根州','votes':16,'time':1},
    {'name':'乔治亚州''votes':16,'time':1},
    {'name':'北卡罗来纳州''votes':15,'time':1}
]

递归求解

第一种办法,递归求解。

对于每一个州,你有两种选择:去或者不去。

如果去,则获得的选票是:这个州的选票 + 剩下时间里去剩下州能获得的最多票数

如果不去,则获得的选票是:剩下时间(这一次不去就没花时间)里去剩下州能获得的最多票数。

最后,比较去或者不去的结果,选择更优的方案。

这里,把剩下时间里去剩下州能获得的最多票数定义为一个函数,随着上面问题的拆解,不断递归:

# 递归解决
# 在指定索引后的州中,剩余时间内,能获得的最多选票
def recurse_solution(states, index, time):

    if len(states) == 0 or index >= len(states) or time <= 0:
        return 0

    # 去这个州(时间还够的话)
    a = 0
    if states[index]['time'] <= time:
        a = states[index]['votes'] + recurse_solution(states, index + 1, time-states[index]['time'])

    # 不去这个州
    b = recurse_solution(states, index + 1, time)

    return max(a, b)

def main():
    print("max votes: %d" % recurse_solution(all_states, 010))

记忆化搜索

上面的递归过程,如同一个二叉树,从根节点不断分叉成:去 / 不去 两个分支,直到叶子节点(剩下州或剩下时间为0)。

然后选出各个路径中和最大的那一条。

递归求解会有很多重叠子问题,就如同那个二叉树中会有很多重叠的子树,重复计算浪费很多时间。

新的方案中引入一个记忆存储memo,定义为指定索引后的州中,剩余时间内,能获得的最多选票,每次计算完后将其记录在案,后续遇到直接查表,不再重复计算:

# 引入记忆化搜索
# memo[index][time]: 在指定索引后的州中,剩余时间内,能获得的最多选票
memo = [[0 for i in range(100)] for j in range(100)]
def memo_search_solution(states, index, time):

    if len(states) == 0 or index >= len(states) or time <= 0:
        return 0

    # 如果记忆表中存有历史结果,直接使用
    if memo[index][time] != 0:
        return memo[index][time]

    # 去这个州(时间还够的话)
    a = 0
    if states[index]['time'] <= time:
        a = states[index]['votes'] + memo_search_solution(states, index + 1, time-states[index]['time'])

    # 不去这个州
    b = memo_search_solution(states, index + 1, time)

    # 记录这次结果,供下次使用
    memo[index][time] = max(a, b)

    return max(a, b)

def main():
    print("max votes: %d" % memo_search_solution(all_states, 010))

动态规划

上面的递归和引入记忆化搜索后的递归,都是自顶向下的思考这个问题:在去与不去两种方案中选择。接着再继续在子问题中再次思考去与不去。

而动态规划则调转枪头,自下而上

先解决只有1个州,只有1天时间,能获得的最大选票

再解决有2个州,只有1天时间,能获得的最大选票

···

再解决全部州,只有1天时间,能获得的最大选票

再解决全部州,有2天时间,能获得的最大选票

···

最后解决全部州,有10天时间,能获得的最大选票

如同正在进行的人口普查,下面每个街道的数据知道了,想知道这个区县的数据就容易了。

知道了每个区县的数据,想知道这个市的数据就容易了。

知道了每个市的数据,想知道这个省的就容易了。

以此类推。

## 动态规划解决
def dp_solution(states, time):

    # memo[index][time]: 在指定索引后的州中,剩余时间内,能获得的最多选票
    memo = [[0 for i in range(time+1)] for j in range(len(states)+1)]

    for i in range(1, len(states) + 1):
        for j in range(1, time+1):
            if states[i - 1]['time'] <= j:
                # 如果时间还够

                # 选择不去
                a = memo[i-1][j]

                # 选择去
                b = memo[i-1][j-states[i-1]['time']] + states[i-1]['votes']

                # 记录去和不去两种选择的最优值
                memo[i][j] = max(a, b)
            else:
                # 如果时间不够
                memo[i][j] = memo[i-1][j]

    return memo[len(states)][time]
    
def main():
    print("max votes: %d" % dp_solution(all_states, 10))

执行上面的代码输出:

max votes: 157

通过上面的代码能够知道特朗普能够获得的最多选票数:157张。

你高高兴兴的告诉特朗普:“Hi,Trump,这10天的宣传活动,你最多能获得157张选票”

但是现在特朗普问你:“去哪些州?行程怎么安排”

你支支吾吾半天没答出来。

特朗普见状说到:“还是让我亲自来,没有人比我更懂动态规划”


推荐阅读

•   吴师兄实名吐槽 LeetCode 上的一道题目。。。•   面试字节跳动时,我竟然遇到了原题……•   计算机专业的学生怎样练习编程才能把编程学精通?•   为什么 MySQL 使用 B+ 树•   一道简简单单的字节跳动算法面试题


欢迎关注我的公众号“五分钟学算法”,如果喜欢,麻烦点一下“在看”~

动态规划:特朗普怎样才能赢?

我还会在以下平台发布内容

GitHub 知乎