贪心算法完全解析

def fractional_knapsack(items, capacity):
    """
    分数背包问题 - 贪心算法
    :param items: 物品列表 [(weight, value), ...]
    :param capacity: 背包容量
    :return: 最大价值
    """
    # 计算单位重量价值，并按其降序排序
    items_with_ratio = [(w, v, v/w) for w, v in items]
    items_with_ratio.sort(key=lambda x: x[2], reverse=True)
    
    total_value = 0
    remaining_capacity = capacity
    
    for weight, value, ratio in items_with_ratio:
        if remaining_capacity <= 0:
            break
        
        # 如果能完全装入
        if weight <= remaining_capacity:
            total_value += value
            remaining_capacity -= weight
        else:
            # 只能装一部分
            fraction = remaining_capacity / weight
            total_value += value * fraction
            remaining_capacity = 0
    
    return total_value

# 测试
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
print(f"最大价值: {fractional_knapsack(items, capacity)}")  # 240.0

import heapq
from collections import Counter

def huffman_encoding(text):
    """
    霍夫曼编码
    :param text: 输入文本
    :return: 编码字典和编码后的文本
    """
    # 统计频率
    freq = Counter(text)
    
    # 构建最小堆
    heap = [[weight, [char, ""]] for char, weight in freq.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]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    # 生成编码字典
    huffman_code = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
    code_dict = {char: code for char, code in huffman_code}
    
    # 编码文本
    encoded_text = ''.join([code_dict[char] for char in text])
    
    return code_dict, encoded_text

# 测试
text = "this is an example of huffman encoding"
code_dict, encoded = huffman_encoding(text)
print("编码字典:", code_dict)
print("原始长度:", len(text) * 8, "bits")
print("编码长度:", len(encoded), "bits")

import heapq

def prim_mst(graph, start):
    """
    Prim 最小生成树算法 - 贪心策略
    :param graph: 邻接表 {节点: [(邻居, 权重), ...]}
    :param start: 起始节点
    :return: MST 的边列表和总权重
    """
    mst_edges = []
    visited = set([start])
    total_weight = 0
    
    # 优先队列：(权重, 从节点, 到节点)
    edges = [(weight, start, neighbor) 
             for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    
    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        
        if v in visited:
            continue
        
        visited.add(v)
        mst_edges.append((u, v, weight))
        total_weight += weight
        
        # 添加新节点的边
        for neighbor, w in graph[v]:
            if neighbor not in visited:
                heapq.heappush(edges, (w, v, neighbor))
    
    return mst_edges, total_weight

# 测试
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}

edges, weight = prim_mst(graph, 'A')
print("MST 边:")
for u, v, w in edges:
    print(f"{u} - {v}: {w}")
print(f"总权重: {weight}")