面试必会--详解动态规划!!通过python学习一个很难的算法
本帖最后由 yx_robert 于 2019-5-23 11:06 编辑面试大厂做算法题 比如百度,头条,腾讯(北京地区面试我所知道的大厂)
动态算法是其中最难啃的题目之一
正好最近在公司内部做了一次技术分享
也把这些打包给大家
干货代码就直接贴出来了 详解!!!
自己整理的ppt文档啥的也分享给大家
希望大家都能够掌握这个算法
(真的很详细 化难为易 我们组的美术哥们都听懂了- -!)
代码配合ppt食用更佳
#! /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 > 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) + tab
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 > 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, m_record) + tab
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 =
result =
print(pre_result)
# 初始化第一行边界 1个矿的情况
for i in range(num + 1): # [0 -- num)
if tab > i:
pre_result = 0
else:
pre_result = tab
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 = 0
elif j >= tab:
# 转移方程(核心)
a = pre_result
b = pre_result[(j - tab)] + tab
result = a if a > b else b
else:
result = pre_result
#
print(result)
# 记录上一层数据
for k in range(num + 1):
pre_result = result
return result
# 题目：
# 有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。
# 参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。
# 要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿
# data
worker_num = 10
# 金子数量, 需要人数
tab_gold_mine = [
,
,
,
,
,
]
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()
新日安 发表于 2019-7-2 17:18
emmm源代码其中两个文件中有错误 for循环后面的冒号 和下面的缩进
文本编译器问题
源文件可运行可调式 ？？代码在哪里？ 啥也没有呀。。楼主忘了上传了 没有内容。楼主是不是上传失误了？ 本帖最后由 yx_robert 于 2019-5-23 11:06 编辑
pdstvs 发表于 2019-5-23 11:04
没有内容。楼主是不是上传失误了？
刚编辑完 有个小错误 现在看不懂，以后不知道能不能用到 刚学python 收藏了 感谢分享 感谢分享 太难了
搞这么多正经的东西连6点热心值都混不到
....
学习了，回家仔细看看学习一下
页:
[1]
2