python算法技巧——动态规划算法练习及掌握

python算法技巧——动态规划算法练习及掌握,第1张

目录

1. 处理爬楼梯的问题

2. 募捐基金问题

3. 最小经费粉刷房子问题

4. 篱笆粉刷方法数量问题

5. 机器人在地图上的路径走法问题 

6. 背包问题


1. 处理爬楼梯的问题

        设计climbstairs(n)进行处理,参数n代表n阶楼梯,每次可以爬1或2阶楼梯,得出有几种爬法可以爬上顶楼;

def  climbstairs(n):
    prev, cur = 1, 1
    for i in range(1, n):
        prev, cur = cur, prev+cur
    return cur
print(climbstairs(2))
print(climbstairs(4))

2. 募捐基金问题

设计col(nums)函数计算最多可以募捐多少价值的物品,在募捐时不可以拜访连续的房子;

def col(nums):
    prev = cur = 0
    for money in nums:
        prev, cur = cur, max(prev+money, cur)
    return cur
print(col([1,2,3,1]))
print(col([2,7,9,3,1]))

3. 最小经费粉刷房子问题

        设计mincost(costs),由于粉刷房子有red、blue、green三种颜色,没见房子粉刷不用颜色会有不同的价格,同时所有相邻的房子不可以刷相同的颜色; 

        粉刷房子的颜色用数组表示,参数costs是相关信息,如:costs[0][0]指的是房子0粉刷红色的费用;

def mincost(costs):
    red = 0
    blue = 0
    green = 0
    for r,b,g in costs:
        red, blue, green = r+min(blue,green), b+min(red,green), g+min(red,blue)
    return min(red,blue,green)
print(mincost([[17,2,14],[15,16,5],[14,3,18]]))

4. 篱笆粉刷方法数量问题

        设计numways(n,k),参数n代表篱笆数量,k代表油漆颜色数量,在粉刷时不可以有超过连续两个篱笆使用相同颜色;

def numways(n,k):
    if n==0:
        return n
    if n==1:
        return k
    same = k
    diff = k*(k-1)
    for i in range(3,n+1):
        same, diff = diff, (same+diff)*(k-1)
    return same+diff
print(numways(4,2))

代码解读: 

         对于这个程序,首先的n=0和1的情况应该不用多说,而当n=2时,有两种情况:

  • 和前一个篱笆相同,有k*1种方法,此时我们的变量名定为same;
  • 和前一个篱笆不相同,有k*(k-1)种方法,此时我们的变量名定为diff;

        而当n>=3时,因为有条件限制不可以有超过两种颜色相同,所以可以如下分析:

  • 下一个篱笆绘制相同颜色的变量计算方式为:same=diff;
  • 绘制不同颜色的变量计算方式为:diff = (same+diff)*(k-1)

        最后我们只需要回传same+diff的总和就好了;


5. 机器人在地图上的路径走法问题 

        设计uniquepaths(m,n)记录机器人邹尼地图上的左上角到地图右下角有几种走法,参数m是地图方格的row,参数n是地图方格的column,机器人的起点是在地图(0,0)位置,机器人的终点是在地图上(m-1,n-1)位置;

        且机器人只可以往右走或是往下走,求共有多少种走法:

def uniquepaths(m,n):
    map = [[0 for i in range(n)]for j in range(m)]
    for i in range(m):
        for j in range(n):
            if i==0 or j==0:
                map[i][j]=1
            else:
                map[i][j] = map[i-1][j]+map[i][j-1]
    return map[m-1][n-1]
print(uniquepaths(3,2))
print(uniquepaths(7,3))

         这个程序是使用了map二维数组记录机器人有多少种走法,记录方法如下:

  • 凡是row=0或column=0,表示走法只有一种;
  • 其他方格的走法则是“左边方格的走法”+“上方方格的走法之和”;

6. 背包问题

        一个人有一个可以装10千克货物的背包,他到一个市场想最大价值的带走他想要的东西,请你用贪心算法帮他:

  • item = ['手表','手机','平板','电脑','相机','眼镜','耳机']

  • value = [1500, 3500, 3800, 4000, 2000, 1200, 1000]

  • weight_things = [2, 4, 5, 8, 3, 1, 1]

def bag(w, wt, val):
    n = len(val)
    table = [[0 for x in range(w+1)] for x in range(n+1)]
    items = [[[]for x in range(w+1)] for x in range(n+1)]
    for r in range(n+1):
        for c in range(w+1):
            if r==0 or c==0:
                table[r][c] = 0
            elif wt[r-1] <= c:
                cur = val[r-1] + table[r-1][c-wt[r-1]]
                cur_items = []
                cur_items.append(item[r-1])
                if items[r-1][c-wt[r-1]]:
                    cur_items += items[r-1][c-wt[r-1]]
                pre = table[r-1][c]
                pre_items = items[r-1][c]
                if cur > pre:
                    table[r][c] = cur
                    items[r][c] = cur_items
                else:
                    table[r][c] = pre
                    items[r][c] = pre_items
            else:
                table[r][c] = table[r-1][c]
                items[r][c] = items[r-1][c]
    return items, table[n][w]


item = ['手表','手机','平板','电脑','相机','眼镜','耳机']
value = [1500, 3500, 3800, 4000, 2000, 1200, 1000]
weight_things = [2, 4, 5, 8, 3, 1, 1]
bag_weight = 10
items, total_value = bag(bag_weight, weight_things, value)
print('最大价值为:', total_value)
print('商品组合为:', items[len(item)][bag_weight])

算法技巧专栏

https://blog.csdn.net/weixin_53919192/category_11761989.htmlhttps://blog.csdn.net/weixin_53919192/category_11761989.html

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/799471.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-06
下一篇 2022-05-06

发表评论

登录后才能评论

评论列表(0条)

保存