用运用动态规划，帮助特朗普赢得选举
states_dict = [{'name': 'Maine', 'votes': 5, 'days': 1},{'name': 'Nevada', 'votes': 6, 'days': 1},{'name': 'Minnesota', 'votes': 10, 'days': 2},{'name': 'New Hampshire', 'votes': 4, 'days': 1},{'name': 'Michigan', 'votes': 16, 'days': 3},{'name': 'Pennsylvania', 'votes': 20, 'days': 4},{'name': 'Wisconsin', 'votes': 10, 'days': 2},{'name': 'Florida', 'votes': 29, 'days': 5},{'name': 'Arizona', 'votes': 11, 'days': 2},{'name': 'North Carolina', 'votes': 15, 'days': 3},{'name': 'Georgia', 'votes': 16, 'days': 3},]
def max_vote_recursive(states, days_left, index):# Terminating conditionsif len(states) == 0 or index >= len(states) or days_left <= 0:return 0# If we have enough days, go to this statevotes_if_go = 0if states[index]['days'] <= days_left:votes_if_go = states[index]['votes'] + max_vote_recursive(states, days_left - states[index]['days'], index + 1)# If we don't go to this statevotes_if_not_go = max_vote_recursive(states, days_left, index + 1)return max(votes_if_go, votes_if_not_go)
if votes_if_go > votes_if_not_go:print(f'There are {days_left} days left. We should go to {states[index]["name"]}')return votes_if_goelse:print(f'There are {days_left} days left. We should not go to {states[index]["name"]}')return votes_if_not_go
There are 2 days left. We should not go to GeorgiaThere are 2 days left. We should not go to North CarolinaThere are 2 days left. We should go to ArizonaThere are 2 days left. We should not go to FloridaThere are 2 days left. We should not go to WisconsinThere are 2 days left. We should not go to PennsylvaniaThere are 1 days left. We should not go to GeorgiaThere are 1 days left. We should not go to North CarolinaThere are 1 days left. We should not go to ArizonaThere are 1 days left. We should not go to FloridaThere are 1 days left. We should not go to WisconsinThere are 1 days left. We should not go to GeorgiaThere are 1 days left. We should not go to North Carolina...
('There are 1 days left. We should not go to Georgia', 74),('There are 2 days left. We should not go to Georgia', 63),('There are 3 days left. We should go to Georgia', 51),('There are 1 days left. We should not go to North Carolina', 45),('There are 2 days left. We should not go to North Carolina', 41),('There are 4 days left. We should go to Georgia', 40),('There are 3 days left. We should not go to North Carolina', 35),('There are 4 days left. We should not go to North Carolina', 29),('There are 5 days left. We should go to Georgia', 28),('There are 1 days left. We should not go to Arizona', 24),('There are 2 days left. We should go to Arizona', 23),('There are 5 days left. We should not go to North Carolina', 22),('There are 3 days left. We should not go to Arizona', 21),('There are 6 days left. We should go to Georgia', 19),('There are 4 days left. We should not go to Arizona', 18),('There are 3 days left. We should not go to Florida', 16),('There are 6 days left. We should go to North Carolina', 16),('There are 2 days left. We should not go to Florida', 15),('There are 4 days left. We should not go to Florida', 15),('There are 5 days left. We should go to Arizona', 14),('There are 1 days left. We should not go to Florida', 13),('There are 5 days left. We should go to Florida', 13),('There are 7 days left. We should go to Georgia', 12),('There are 6 days left. We should not go to Arizona', 11),('There are 6 days left. We should not go to Florida', 11),('There are 7 days left. We should go to North Carolina', 11),...
要解决的问题必须分为子问题。 在自下而上的推理过程中，我们必须确保在给定条件下，每个步骤（子问题）均已全局优化。
def max_vote_dynamic_planning(states, total_days):dp_matrix = [[0 for days_left in range(total_days + 1)] for index in range(len(states) + 1)]for index in range(1, len(states) + 1):for days_left in range(1, total_days + 1):if states[index-1]['days'] <= days_left: # If we have enough days leftvotes_if_go = dp_matrix[index-1][days_left - states[index-1]['days']] + states[index-1]['votes']votes_if_not_go = dp_matrix[index-1][days_left]# Save the maximum votes into cachedp_matrix[index][days_left] = max(votes_if_go, votes_if_not_go)else: # We don't have any days leftdp_matrix[index][days_left] = dp_matrix[index-1][days_left]return dp_matrix[-1][-1]max_vote_dynamic_planning(states_dict, 10)
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],[0, 6, 11, 11, 11, 11, 11, 11, 11, 11, 11],[0, 6, 11, 16, 21, 21, 21, 21, 21, 21, 21],[0, 6, 11, 16, 21, 25, 25, 25, 25, 25, 25],[0, 6, 11, 16, 22, 27, 32, 37, 41, 41, 41],[0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],[0, 6, 11, 16, 22, 27, 32, 37, 42, 47, 52],[0, 6, 11, 16, 22, 29, 35, 40, 45, 51, 56],[0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],[0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56],[0, 6, 11, 17, 22, 29, 35, 40, 46, 51, 56]]
初始化一个二维矩阵，该二维矩阵使用状态数作为行、天数作为列。 从剩余天数为1（索引= 1）开始搜索。 如果我们转到当前州，应该将该州的选举人票数与剩余天数所能获得的最高票数相加。剩余天数应为当前剩余天数减去当前状态下我们需要提升的天数。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~
评论