利用贪心法求解旅行商问题和背包问题。给出代码

1. 旅行商问题的贪心算法代码：

def tsp(graph, start):
    # 从起点开始
    current = start  
    path = [current]
    # 遍历所有节点
    while len(path) < len(graph):
        # 将当前节点和所有未访问过的节点距离存储到列表中
        distances = [(i, graph[current][i]) for i in range(len(graph)) if i not in path]
        # 根据距离升序排序
        distances = sorted(distances, key=lambda x: x[1])
        # 取最短距离的节点作为下一个节点
        next_node = distances[0][0]
        path.append(next_node)
        current = next_node
    # 最后回到起点
    path.append(start)
    return path

2. 背包问题的贪心算法代码：

def knapsack(items, capacity):
    # 按单位价值排序
    items = sorted(items, key=lambda x: x[2], reverse=True)
    # 初始化总价值和总重量
    total_value = 0
    total_weight = 0
    for item in items:
        # 如果当前物品能够放下
        if total_weight + item[1] <= capacity:
            total_weight += item[1]
            total_value += item[0]
        else:
            # 放不下就按比例装满
            remaining_capacity = capacity - total_weight
            total_value += item[2] * remaining_capacity
            break
    return total_value

其中 `items` 是一个元组列表，每个元组包含物品的价值、重量和单位价值（价值/重量）。`capacity` 是背包的容量。