0/1 背包问题贪心算法求解及 Python 代码实现

例如，4 个物品重量为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量 C-10。

首先，将给定物品按单位重量价值从大到小排序

应用贪心法求得近似解为(1, 0, 1, 0)，获得的价值为 65，这可以作为 0/1 背包问题的下界。

人考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则 ub=Cx(vi/w)=10x10=100。

于是，得到了目标函数的界[65, 100]。

表11-1 0/1 背包问题的价值/重量排结果

物品 | 重量(ws) | 价值(v) | 价值/重量(w/w) ------- | -------- | -------- | -------- 1 | 4 | 40 | 10 0 | 7 | 12 | 1.71 3 | 5 | 25 | 5 2 | 3 | 42 | 14

代码实现

以下是一个 Python 代码实现：

def fractional_knapsack(weights, values, capacity):
    n = len(weights)
    # 计算单位重量价值
    unit_values = [(values[i]/weights[i], i) for i in range(n)]
    # 按单位重量价值从大到小排序
    unit_values.sort(reverse=True)
    # 初始化总价值和当前背包容量
    total_value = 0
    current_capacity = 0
    # 依次考虑每个物品
    for unit_value, i in unit_values:
        # 如果该物品可以全部装入背包
        if weights[i] + current_capacity <= capacity:
            total_value += values[i]
            current_capacity += weights[i]
        # 否则只装入一部分
        else:
            fraction = (capacity - current_capacity) / weights[i]
            total_value += fraction * values[i]
            current_capacity = capacity
            break
    return total_value

weights = [4, 7, 5, 3]
values = [40, 12, 25, 42]
capacity = 10
print(fractional_knapsack(weights, values, capacity)) # 输出 65.0