面试必会--详解动态规划!!通过python学习一个很难的算法

本文来源吾爱破解论坛

本帖最后由 yx_robert 于 2019-5-23 11:06 编辑

面试大厂做算法题 比如百度,头条,腾讯(北京地区面试我所知道的大厂)
动态算法是其中最难啃的题目之一
正好最近在公司内部做了一次技术分享
也把这些打包给大家
干货代码就直接贴出来了 详解!!!
自己整理的ppt文档啥的也分享给大家
希望大家都能够掌握这个算法
(真的很详细 化难为易 我们组的美术哥们都听懂了- -!)
代码配合ppt食用更佳

[Python] 纯文本查看 复制代码

#! /usr/bin/env python
# -*- coding: UTF-8 -*-

import time

# 1.递归
def func_1(tab, index, num):
        # 边界判断
        if num <= 0 or index >= len(tab):
                return 0

        # 人数不够直接返回
        if tab[index][1] > num:
                return func_1(tab, index + 1, num)

        # 转移方程(核心)
        a = b = 0
        a = func_1(tab, index + 1, num)
        b = func_1(tab, index + 1, num - tab[index][1]) + tab[index][0]
        if a >= b:
                return a
        else:
                return b

# 2.递归优化(备忘录算法解法)
def func_2(tab, index, num, m_record):
        # 边界判断
        if num <= 0 or index >= len(tab):
                return 0

        # 人数不够直接返回
        if tab[index][1] > num:
                return func_2(tab, index + 1, num, m_record)

        # 记录在案 直接返回结果
        if (index, num) in m_record:
                return m_record[(index, num)]

        # 转移方程(核心)
        a = b = 0
        a = func_2(tab, index + 1, num, m_record)
        b = func_2(tab, index + 1, num - tab[index][1], m_record) + tab[index][0]
        if a >= b:
                # 记录某种状态下的最优解
                m_record[(index, num)] = a
                return a
        else:
                # 记录某种状态下的最优解
                m_record[(index, num)] = b
                return b

# 3.动态规划方法
def func_3(tab, index, num):
        print("3.动态规划方法\n")
        # 从0到10人 0是为了方便边界处理
        # 没多一个矿的最优解只和上一层的结果相关
        # 故保留上一层的数据pre_result
        pre_result = [0 for i in range(num + 1)]
        result = [0 for i in range(num + 1)] 
        print(pre_result)

        # 初始化第一行边界 1个矿的情况
        for i in range(num + 1): # [0 -- num)
                if tab[0][1] > i:
                        pre_result[i] = 0
                else:
                        pre_result[i] = tab[0][0]

        print("boarder:")
        print(pre_result)
        print("\n")

        # 外层循环矿的数量
        for i in range(1, len(tab)):
        # for i in range(1, 4):
                # 内层循环人数
                for j in range(num + 1):
                        if j == 0:
                                # 第一列边界
                                result[j] = 0
                        elif j >= tab[i][1]:
                                # 转移方程(核心)
                                a = pre_result[j]
                                b = pre_result[(j - tab[i][1])] + tab[i][0]
                                result[j] = a if a > b else b
                        else:
                                result[j] = pre_result[j]

                # 
                print(result)
                # 记录上一层数据
                for k in range(num + 1):
                        pre_result[k] = result[k]

        return result[num]


# 题目：
# 有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。
# 参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。
# 要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿

# data
worker_num = 10
# 金子数量, 需要人数
tab_gold_mine = [
        [400, 5] ,
        [500, 5] ,
        [200, 3] ,
        [300, 4] ,
        [350, 3] ,
]

def main():

        # start = time.time()
        # print(start)

        # 1.递归
        val = func_1(tab_gold_mine, 0, worker_num)

        # 2.递归优化(备忘录算法解法)
        map_record = {}
        val = func_2(tab_gold_mine, 0, worker_num, map_record)
        # print(map_record)

        # 3.动态规划方法
        val = func_3(tab_gold_mine, 0, worker_num)

        # end = time.time()
        # print(end)
        # print("时间消耗:%f" % (end - start))

        print(val)

if __name__ == "__main__":
        main()

dynamic_programming.rar

2019-5-23 11:03 上传

点击文件名下载附件

下载积分: 吾爱币 -1 CB

357.52 KB, 下载次数: 189, 下载积分: 吾爱币 -1 CB

宣讲文档ppt