子网选择问题

子网选择问题是一个经典的组合优化问题，其目标是在给定的一组子网中选择一些子网，使得这些子网的总费用最小，同时满足一定的带宽需求。

下面是一个基于贪心算法的解决方法的代码示例：

def subnet_selection(subnets, bandwidth):
    # subnets: 子网列表，每个子网是一个元组 (带宽, 费用)
    # bandwidth: 带宽需求
    # 返回值: 选择的子网的索引列表

    # 根据费用从小到大对子网进行排序
    sorted_subnets = sorted(subnets, key=lambda x: x[1])
    
    selected_subnets = []  # 选择的子网列表
    total_bandwidth = 0  # 已选择子网的总带宽
    
    for i in range(len(sorted_subnets)):
        if total_bandwidth >= bandwidth:
            break
        
        if sorted_subnets[i][0] + total_bandwidth <= bandwidth:
            selected_subnets.append(i)
            total_bandwidth += sorted_subnets[i][0]
    
    return selected_subnets

使用示例：

subnets = [(10, 50), (20, 30), (30, 40), (5, 20)]
bandwidth = 40

selected = subnet_selection(subnets, bandwidth)
print(selected)  # 输出 [1, 0]

在上面的示例中，我们有4个子网，每个子网都有不同的带宽和费用。带宽需求是40。我们使用subnet_selection函数选择了满足带宽需求的子网，并返回了选中子网的索引列表。在这个例子中，选择了第2个和第1个子网，它们的总带宽为30 + 20 = 50，满足了带宽需求。