生成贪心算法实现背包问题的程序

以下是一个简单的贪心算法实现背包问题的程序，其中使用了贪心策略：每次选择单位重量价值最大的物品放入背包中。

def knapsack(W, wt, val):
    n = len(val)
    # 计算每个物品的单位重量价值
    cost = [val[i] / wt[i] for i in range(n)]
    # 按单位重量价值从大到小排序
    items = sorted(zip(cost, wt, val), reverse=True)
    # 初始化背包和总价值
    res = [0] * n
    total_val = 0
    # 使用贪心策略，每次选择单位重量价值最大的物品放入背包中
    for i in range(n):
        if items[i][1] <= W:
            res[i] = 1
            W -= items[i][1]
            total_val += items[i][2]
        else:
            res[i] = W / items[i][1]
            total_val += res[i] * items[i][2]
            break
    return total_val, res

其中，函数 `knapsack` 接受三个参数：背包容量 `W`，物品重量列表 `wt`，物品价值列表 `val`。函数返回两个值：可获得的最大总价值和每个物品是否被放入背包中的列表。

这个实现的时间复杂度为 $O(n\log n)$，其中 $n$ 是物品的数量。