def greedy_coin_change(coins, target):
    """
    使用贪婪算法找到目标金额的最少硬币数量
    
    参数:
        coins: 一个列表，包含不同面额的硬币
        target: 目标金额
        
    返回:
        result: 一个字典，包含用到的每种硬币的数量
    """
    # 将硬币按面值从大到小排序，以便我们可以先使用最大面额的硬币
    coins.sort(reverse=True)
    
    # 初始化一个字典用来存储每种硬币的使用数量
    result = {coin: 0 for coin in coins}
    
    # 遍历所有硬币面额
    for coin in coins:
        # 如果目标金额大于0，我们还需要继续找零
        if target > 0:
            # 使用当前面额的硬币数量是目标金额除以硬币面额
            # 使用整除（//）得到的商表示我们用到的硬币数量
            num_coins = target // coin
            # 更新目标金额，减去已经通过当前硬币找到的金额
            target -= num_coins * coin
            # 在结果字典中更新当前硬币的数量
            result[coin] = num_coins
    
    # 返回包含每种硬币数量的字典
    return result

def fractional_knapsack(items, capacity):
    """
    使用贪婪算法解决分数背包问题
    
    参数:
        items: 一个列表，每个元素是一个元组(value, weight)表示每个物品的价值和重量
        capacity: 背包的最大承重
        
    返回:
        chosen_items: 一个列表，包含被选中的物品及其对应的部分比例
        max_value: 背包中物品的最大总价值
    """
    # 计算每个物品的单位重量价值，并按单位重量价值降序排序
    # 其中, item_value_per_weight = (index, value/weight)
    items_value_per_weight = sorted(
        [(index, value / weight) for index, (value, weight) in enumerate(items)], 
        key=lambda x: x[1], 
        reverse=True
    )
    
    # 初始化最大价值和选择物品的列表
    max_value = 0
    chosen_items = []
    
    # 遍历按单位重量价值排序的物品
    for index, value_per_weight in items_value_per_weight:
        # 获取物品的价值和重量
        value, weight = items[index]
        
        # 如果物品的重量小于背包的剩余容量
        if weight <= capacity:
            # 将物品完全放入背包
            chosen_items.append((index, 1))
            # 更新最大价值和背包的剩余容量
            max_value += value
            capacity -= weight
        else:
            # 如果物品的重量大于背包的剩余容量，只放入一部分
            fraction = capacity / weight
            chosen_items.append((index, fraction))
            # 更新最大价值
            max_value += value * fraction
            # 背包已满，退出循环
            break
    
    # 返回选择的物品及其比例，以及物品的最大总价值
    return chosen_items, max_value

import heapq  # 使用heapq来创建一个最小堆
from collections import defaultdict, Counter  # 使用defaultdict来创建一个默认字典，使用Counter来计算字符的频率

def encode_huffman(data):
    """
    Huffman 编码实现
    
    参数:
        data: 需要编码的字符串数据
        
    返回:
        编码字典，用于查询每个字符的Huffman编码
    """
    # 使用Counter计算每个字符的频率，并构造一个最小堆
    heap = [[weight, [char, ""]] for char, weight in Counter(data).items()]
    heapq.heapify(heap)
    
    # 当堆中仅有一个元素时，所有字符的Huffman编码已完成
    while len(heap) > 1:
        # 弹出两个权重最小的元素
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        
        # 更新这两个元素中所有字符的编码
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        # 将两个元素合并后放回堆中
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
        
    # 生成编码字典，用于查询
    codes = dict(heapq.heappop(heap)[1:])
    return codes

def decode_huffman(encoded_data, codes):
    """
    Huffman 解码实现
    
    参数:
        encoded_data: Huffman编码的二进制字符串
        codes: 编码表，一个字典，包含原始数据中每个字符及其对应的Huffman编码
        
    返回:
        原始数据字符串
    """
    # 翻转编码表的键值对，以便我们可以使用Huffman编码查找对应的字符
    reversed_codes = {code: char for char, code in codes.items()}
    
    # 初始化解码字符串和临时存储的编码
    decoded_data = ""
    temp_code = ""
    
    # 遍历编码的二进制字符串的每个字符
    for bit in encoded_data:
        # 将当前位添加到临时编码中
        temp_code += bit
        # 如果这个临时编码在编码表中存在，将对应的字符添加到解码字符串中
        if temp_code in reversed_codes:
            decoded_data += reversed_codes[temp_code]
            # 清空临时编码，以便解码下一个字符
            temp_code = ""
    
    # 返回解码后的字符串
    return decoded_data

import numpy as np  # 导入NumPy库，用于数值运算

def greedy_tsp(distances):
    """
    使用贪婪算法解决旅行商问题
    
    参数:
        distances: 一个二维数组，表示每对城市之间的距离
        
    返回:
        path: 一个列表，表示旅行商访问城市的顺序
        total_distance: 总的旅行距离
    """
    # 获取城市的数量
    num_cities = len(distances)
    
    # 初始化路径和总距离
    path = [0]  # 从第一个城市开始
    total_distance = 0
    
    # 初始化一个集合，用于存储已访问的城市
    visited = set([0])
    
    # 循环直到所有城市都被访问
    while len(path) < num_cities:
        # 获取当前城市
        current_city = path[-1]
        
        # 获取所有未访问城市到当前城市的距离
        distances_to_current = distances[current_city]
        
        # 初始化最小距离为无穷大
        min_distance = np.inf
        # 初始化下一个要访问的城市为None
        next_city = None
        
        # 遍历所有城市
        for i in range(num_cities):
            # 如果城市未被访问且到当前城市的距离小于已知的最小距离
            if i not in visited and distances_to_current[i] < min_distance:
                # 更新最小距离和下一个要访问的城市
                min_distance = distances_to_current[i]
                next_city = i
        
        # 将下一个城市添加到路径中，并更新总距离和已访问的城市集合
        path.append(next_city)
        total_distance += min_distance
        visited.add(next_city)
    
    # 从最后一个访问的城市返回到起始城市，并更新总距离
    path.append(path[0])
    total_distance += distances[path[-2]][path[-1]]
    
    # 返回路径和总距离
    return path, total_distance

def activity_selection(activities):
    """
    使用贪婪算法解决活动选择问题
    
    参数:
        activities: 一个列表，每个元素是一个元组(start, finish)，表示活动的开始和结束时间
        
    返回:
        selected_activities: 一个列表，包含被选中的活动的开始和结束时间
    """
    # 将活动按结束时间升序排序
    activities.sort(key=lambda activity: activity[1])
    
    # 初始化选中的活动列表，并将第一个活动添加到列表中
    selected_activities = [activities[0]]
    
    # 遍历剩下的活动
    for i in range(1, len(activities)):
        # 如果活动的开始时间大于或等于前一个选中活动的结束时间，则选中该活动
        if activities[i][0] >= selected_activities[-1][1]:
            selected_activities.append(activities[i])
    
    # 返回选中的活动列表
    return selected_activities

def coin_change_greedy(coins, amount):
    """
    使用贪婪算法解决零钱兑换问题
    
    参数:
        coins: 一个列表，包含不同面值硬币的整数值
        amount: 需要找零的金额，一个整数
        
    返回:
        used_coins: 一个列表，包含用于找零的硬币的面值
    """
    # 将硬币面值按降序排序，以便我们可以优先使用面值大的硬币
    coins.sort(reverse=True)
    
    # 初始化用于找零的硬币列表
    used_coins = []
    
    # 对每种硬币进行遍历
    for coin in coins:
        # 计算每种硬币需要使用的数量，并更新需要找零的金额
        while amount >= coin:
            amount -= coin
            used_coins.append(coin)
    
    # 如果最后找零的金额为0，返回用于找零的硬币列表，否则表示无法找零
    return used_coins if amount == 0 else None

def fractional_knapsack(items, W):
    """
    使用贪婪算法解决分数背包问题
    
    参数:
        items: 一个列表，每个元素是一个元组(value, weight)，表示物品的价值和重量
        W: 背包的最大容量
        
    返回:
        total_value: 背包中物品的总价值
        fractions: 一个列表，包含每件物品在背包中的数量（可以是分数）
    """
    # 计算每件物品的单位重量价值，并按降序排序
    items_sorted = sorted(items, key=lambda item: item[0]/item[1], reverse=True)
    
    # 初始化总价值和物品数量列表
    total_value = 0
    fractions = [0] * len(items)
    
    # 遍历排序后的物品
    for i, (value, weight) in enumerate(items_sorted):
        # 如果背包可以容纳整个物品，放入整个物品
        if W >= weight:
            fractions[i] = 1
            total_value += value
            W -= weight
        else:
            # 如果背包只能容纳部分物品，放入尽可能多的物品
            fraction = W / weight
            fractions[i] = fraction
            total_value += value * fraction
            break  # 背包已满，结束循环
    
    # 返回总价值和物品数量列表
    return total_value, fractions

def find_parent(x, parents):
    """
    使用路径压缩查找元素x的根节点
    
    参数:
        x: 元素
        parents: 一个列表，表示每个元素的父节点
        
    返回:
        x的根节点
    """
    if parents[x] != x:
        parents[x] = find_parent(parents[x], parents)  # 路径压缩
    return parents[x]

def union(x, y, parents):
    """
    将x和y所在的集合合并
    
    参数:
        x, y: 元素
        parents: 一个列表，表示每个元素的父节点
    """
    root_x = find_parent(x, parents)
    root_y = find_parent(y, parents)
    if root_x != root_y:
        parents[root_x] = root_y

def kruskal_algorithm(edges, num_nodes):
    """
    使用Kruskal算法找到图的最小生成树
    
    参数:
        edges: 一个列表，每个元素是一个元组(u, v, w)，表示一条连接u和v的权重为w的边
        num_nodes: 图中节点的数量
        
    返回:
        min_span_tree: 一个列表，包含最小生成树中的边
    """
    # 将边按权重升序排序
    edges.sort(key=lambda edge: edge[2])
    
    # 初始化每个节点的父节点为其自身
    parents = list(range(num_nodes))
    
    # 初始化最小生成树的边列表
    min_span_tree = []
    
    # 遍历所有的边
    for u, v, w in edges:
        # 如果u和v不在同一个集合中，将边(u, v)添加到最小生成树中，并合并u和v所在的集合
        if find_parent(u, parents) != find_parent(v, parents):
            min_span_tree.append((u, v, w))
            union(u, v, parents)
    
    # 返回最小生成树的边
    return min_span_tree

import heapq  # 导入堆队列（优先队列）模块
from collections import defaultdict, Counter  # 导入默认字典和计数器模块

def huffman_encoding(data):
    """
    使用霍夫曼算法进行数据编码
    
    参数:
        data: 一个字符串，包含要编码的数据
        
    返回:
        encoding: 一个字典，包含每个字符及其对应的霍夫曼编码
    """
    # 使用计数器获取每个字符及其出现的频率
    frequency = Counter(data)
    
    # 使用优先队列（最小堆）和频率数据创建一个霍夫曼树
    heap = [[weight, [char, ""]] for char, weight in frequency.items()]
    heapq.heapify(heap)
    
    # 循环直到堆中只剩下一个节点
    while len(heap) > 1:
        lo = heapq.heappop(heap)  # 获取频率最小的节点
        hi = heapq.heappop(heap)  # 获取频率次小的节点
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]  # 在频率最小的节点的编码前添加'0'
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]  # 在频率次小的节点的编码前添加'1'
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])  # 合并节点并添加回堆中
    
    # 获取字符及其对应的霍夫曼编码
    encoding = dict(heapq.heappop(heap)[1:])
    
    # 返回编码字典
    return encoding