【算法进阶1】贪心算法、背包问题(0-1背包、分数背包)、拼接最大数字问题、活动选择问题

1 贪心算法
2 背包问题
2.1 0-1背包问题
2.2 分数背包
3 拼接最大数字问题
4 活动选择问题

1 贪心算法

贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。
要会判断一个问题能否用贪心算法来计算。

from typing import List, Tuple


def change(t: List[int], n: int) -> Tuple[List[int], int]:
    """
    根据可用面额的列表 `t`，计算将金额 `n` 换成不同面额的硬币或纸币的最少数量。

    :param t: 可用面额的列表（整数列表），假设已给定的面额都是正数
    :param n: 需要兑换的金额（整数）
    :return: 一个元组，包含两个元素：
             - 一个列表，其中每个元素表示使用相应面额的数量
             - 剩余未兑换的金额（整数）
    """
    t.sort(reverse=True)  # 按面额从大到小排序，以便优先使用较大面额的货币
    m = [0 for _ in range(len(t))]  # 初始化结果列表 `m`，存储每种面额的使用数量

    # 遍历每一种面额
    for i, money in enumerate(t):
        m[i] = n // money  # 计算当前面额最多可以使用多少次
        n = n % money  # 计算剩余未兑换的金额

    return m, n  # 返回使用的面额数量列表和剩余未兑换的金额


t = [100, 50, 20, 5, 1]
print(change(t, 376))  # ([3, 1, 1, 1, 1], 0)
print(t)  # [100, 50, 20, 5, 1]

2 背包问题

2.1 0-1背包问题

def knapsack(weights: List[int], values: List[int], W: int) -> int:
    """
    0-1 背包问题的解决方案。
    
    :param weights: 每个金条的重量列表
    :param values: 每个金条的价值列表
    :param W: 背包的最大容量
    :return: 背包中可以放入的最大价值
    """
    n = len(weights)
    
    # 初始化 DP 表，行数为金条的数量+1，列数为背包的容量+1
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # 填充 DP 表
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if weights[i-1] <= w:  # 如果当前金条的重量小于等于当前容量
                # 选择放或不放当前金条，取最大值
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                # 不能放当前金条，只能继承前一个状态的值
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]  # 返回背包的最大价值

# 示例
weights = [2, 3, 4, 5]  # 每个金条的重量
values = [3, 4, 5, 6]   # 每个金条的价值
W = 8  # 背包的容量

# 计算最大价值
max_value = knapsack(weights, values, W)
print(max_value)  # 输出 10

2.2分数背包

from typing import List, Tuple


def fractional_backpack(goods: List[Tuple[int, int]], w: int) -> Tuple[float, List[float]]:
    """
    分数背包问题的解决方案（贪心算法）。

    这个算法用于在给定背包容量的情况下，最大化所能获得的总价值，并允许将物品分割成任意比例。

    :param goods: 一个包含物品的列表，每个物品用一个元组表示，其中第一个值是物品的价值，第二个值是物品的重量
    :param w: 背包的容量（整数）
    :return: 一个元组，其中第一个元素是总价值（浮点数），第二个元素是一个列表，表示每种物品被选择的比例
    """
    # 初始化列表 `m` 用于记录每种物品被选择的比例，初始时所有比例为 0
    m = [0.0 for _ in range(len(goods))]

    total_price = 0.0  # 用于累加总价值的变量，初始为 0

    # 遍历每种物品
    for i, (price, weight) in enumerate(goods):
        if w >= weight:
            # 如果背包容量足够放下当前物品，则将整件物品放入背包
            m[i] = 1.0
            total_price += price  # 增加物品的总价值
            w -= weight  # 减少背包剩余容量
        else:
            # 如果背包容量不足以放下整个物品，则只放入物品的一部分
            m[i] = w / weight  # 计算放入的比例
            total_price += m[i] * price  # 增加按比例计算的物品价值
            w = 0  # 背包容量用尽
            break  # 背包已满，停止处理其他物品

    return total_price, m  # 返回总价值和每种物品的选择比例


# 示例用法
goods = [(60, 10), (120, 30), (100, 20)]
goods.sort(key=lambda x: x[0] / x[1], reverse=True)  # 按价值重量比降序排序物品
print(fractional_backpack(goods, 50))  # 输出：最大化价值和每种物品的选择比例

3 拼接最大数字问题

# 数字拼接问题也是贪心算法
a = '96'
b = '87'
res = a + b if a > b else b + a

a = '128'
b = '1286'
res = a + b if a + b > b + a else b + a

实现

from functools import cmp_to_key


def xy_cmp(x: str, y: str) -> int:
    """
    自定义比较函数，用于比较两个字符串 x 和 y 在不同顺序下拼接的结果。

    :param x: 第一个字符串
    :param y: 第二个字符串
    :return: 如果 x + y < y + x 返回 1（表示 y 应排在前面），
             如果 x + y > y + x 返回 -1（表示 x 应排在前面），
             否则返回 0（表示 x 和 y 顺序不变）。
    """
    if x + y < y + x:
        return 1  # y 应该排在 x 前面
    elif x + y > y + x:
        return -1  # x 应该排在 y 前面
    else:
        return 0  # 保持原有顺序


def number_join(li: list) -> str:
    """
    将一组数字组成一个最大可能的数字，数字之间的顺序由自定义的比较规则决定。

    :param li: 包含多个整数的列表
    :return: 拼接后的最大数字（字符串形式）
    """
    # 将整数列表中的每个数字转换为字符串，以便后续拼接操作
    li = list(map(str, li))

    # 使用自定义的比较函数 `xy_cmp` 对字符串列表进行排序
    li.sort(key=cmp_to_key(xy_cmp))

    # 将排序后的字符串列表拼接成一个大的字符串，并返回
    return ''.join(li)


li = [32, 94, 128, 1286, 6, 71]
print(number_join(li))  # 94716321286128

4 活动选择问题

from typing import List, Tuple

# 假设活动列表已经按结束时间排序
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
# 使用 lambda 函数将活动按结束时间排序
activities.sort(key=lambda x: x[1])  # 按照每个活动的结束时间（元组的第二个元素）进行排序


def activities_selection(li: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    """
    选择最大兼容活动的贪心算法。

    该算法在给定的已排序活动列表中选择最大数量的互不冲突的活动，
    使得选择的活动之间没有时间重叠。

    :param li: 按结束时间排序的活动列表，每个活动由一个 (开始时间, 结束时间) 元组表示
    :return: 一个包含最大数量不冲突活动的列表，按活动的选择顺序排列
    """
    res = [li[0]]  # 初始化结果列表，将第一个活动加入到结果中

    # 从第二个活动开始遍历
    for i in range(1, len(li)):
        # 如果当前活动的开始时间大于或等于最后一个选择的活动的结束时间
        if li[i][0] >= res[-1][1]:
            res.append(li[i])  # 将当前活动加入结果列表中

    return res  # 返回包含最大数量不冲突活动的列表


print(activities_selection(activities))