背包问题贪心算法伪代码

以下是基于贪心算法的背包问题伪代码：

1. 初始化总价值和总重量为0
2. 对于每个物品i，计算其性价比，即价值/重量
3. 按照性价比从大到小排序所有物品
4. 对于每个物品i，如果它的重量小于等于背包剩余容量，则将它装入背包中，并更新总价值和总重量
5. 如果物品i的重量大于背包剩余容量，则将它按照比例拆分，将能够装入的部分装入背包中，并更新总价值和总重量
6. 重复步骤4和5，直到所有物品都被考虑

伪代码如下：

function knapsack(weights, values, capacity):
    n = length(weights)
    ratios = [values[i] / weights[i] for i in range(n)]
    sorted_indices = sort_indices(ratios, descending=True)
    total_value = 0
    total_weight = 0
    for i in sorted_indices:
        if weights[i] <= capacity:
            total_value += values[i]
            total_weight += weights[i]
            capacity -= weights[i]
        else:
            fraction = capacity / weights[i]
            total_value += fraction * values[i]
            total_weight += fraction * weights[i]
            break
    return total_value, total_weight