贪心算法背包问题代码运行

贪心算法在解决背包问题时，通常用于求解0-1背包问题或部分背包问题，其中物品有固定的价值和体积（重量），目标是在不超过背包容量的前提下，尽可能获取总价值最大的物品组合。下面是一个简单的Python代码示例，使用贪心策略处理0-1背包问题：

def knapsack_greedy(values, weights, capacity):
    # 创建一个列表来保存选择的物品索引
    chosen_items = []

    for i in range(len(values)):
        if weights[i] <= capacity:
            # 如果当前物品的重量小于等于剩余容量，选择它并更新容量
            capacity -= weights[i]
            chosen_items.append(i)

    # 从值最高的物品开始，尝试回溯补全容量，如果剩余容量大于等于当前物品的价值，则添加
    while capacity > 0 and len(chosen_items) > 0:
        last_item = -1
        max_value = 0
        for i in reversed(range(len(values))):
            if weights[i] <= capacity and values[i] > max_value:
                last_item = i
                max_value = values[i]

        if last_item != -1:
            capacity -= weights[last_item]
            chosen_items.append(last_item)
        else:
            break

    return chosen_items, sum(values[i] for i in chosen_items)


# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("选择的物品:", knapsack_greedy(values, weights, capacity)[0])
print("总价值:", knapsack_greedy(values, weights, capacity)[1])