Python数据结构与算法——算法(贪心算法、动态规划

t = [100, 50, 20, 5, 1]
 
def change(t, n):
    m = [0 for _ in range(len(t))]
    for i, money in enumerate(t):
        m[i] = n // money
        n = n % money
    return m, n
 
print(change(t, 376))

goods = [(60, 10), (120, 30), (100, 20)]  # 每个商品元组表示(价格, 重量)
goods.sort(key = lambda x:x[0]/x[1], reverse = True)  # 按照单价排序
 
def fractional_backpack(goods, w):    
    m = [0 for _ in range(len(goods))]
    total_v = 0
    for i, (price, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            w -= weight
            total_v += price
        else:
            m[i] = w/weight
            total_v += m[i] * price
            w = 0
            break
    return m, total_v
 
 
print(fractional_backpack(goods, 50))

from functools import cmp_to_key
 
li = [32, 94, 128, 1286, 6, 71]
 
def xy_cmp(x, y):
    if x+y > y+x:
        return -1
    elif x+y < y+x:
        return 1
    else:
        return 0
 
def number_join(li):
    li = list(map(str, li))
    li.sort(key=cmp_to_key(xy_cmp))
    return "".join(li)
 
print(number_join(li))

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
 
# 保证活动是按照结束时间排好序的
activities.sort(key=lambda x:x[1])
 
def activity_selection(a):
    res = [a[0]]
    for i in range(1, len(a)):
        if a[i][0] >= res[-1][1]:  # 当前活动的开始时间小于等于最后一个入选活动的结束时间
            res.append(a[i])
    return res
 
print(activity_selection(activities))

# 子问题的重复计算
def fibnacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibnacci(n-1) + fibnacci(n-2)
 
 
# 无重复计算，存在列表中——动态规划(DP)
def fibnacci_no_recurision(n):
    f = [0, 1, 1]
    if n > 2:
        for i in range(n-2):
            num = f[-1] + f[-2]
            f.append(num)
    return f[-1]
 
print(fibnacci_no_recurision(100))

p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
 
def cut_rod_recurision_1(p, n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1, n):
            res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n-i))
    return res
 
 
def cut_rod_recurision_2(p, n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1, n+1):
            res = max(res, p[i] + cut_rod_recurision_2(p, n-i))
    return res
 
print(cut_rod_recurision_1(p, 15))
print(cut_rod_recurision_2(p, 15))

p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
 
def cut_rod_dp(p, n):
    r = [0]
    for i in range(1, n+1):
        res = 0
        for j in range(1, i+1):
            res = max(res, p[j] + r[i-j])
        r.append(res)
    return r[n]
 
print(cut_rod_dp(p, 9))

 
def cut_rod_extend(p, n):
    r = [0]
    s = [0]
    for i in range(1, n+1):
        res_r = 0  # 记录价格的最大值
        res_s = 0  # 记录价格最大值对应方案的左边不切割部分的长度
        for j in range(1, i+1):
            if p[j] + r[i-j] > res_r:
                res_r = p[j] + r[i-j]
                res_s = j
        r.append(res_r)
        s.append(res_s)
    return r[n], s
 
def cut_rod_solution(p, n):
    r, s = cut_rod_extend(p, n)
    ans = []
    while n > 0:
        ans.append(s[n])
        n -= s[n]
    return ans
 
print(cut_rod_solution(p, 9))

def lcs_length(x, y):
    m = len(x)
    n = len(y)
 
    # 创建一个二维数组来存储子问题的解
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    # 填充dp数组
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # i j 位置上的字符匹配时，来自与左上方
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
    # 从dp数组中找到最长公共子序列的长度
    return dp[m][n]
 
 
# 测试
x = "abcde"
y = "ace"
print(lcs_length(x, y))