例如4个物品重量为4753价值分别为40422512背包容量 C-10首先将给定物品按单位重量价值从大到小排序应用贪心法求得近似解为1010获得的价值为 65这可以作为 01背包问题的下界。人考虑最好情况背包中装入的全部是第1个物品且可以将背包装满则ub=Cxviw=10x10=100。于是得到了目标函数的界65100。表11-1 01 背包问题的价值重量排结果物品103重量ws价值v价值重量ww

以下是一个 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.