python分治法求0-1背包问题程序

下面是使用分治法求解0-1背包问题的Python程序：

def fractional_knapsack(w, v, c):
    n = len(w)
    # 用元组表示物品，其中第一个元素是单位重量价值，第二个元素是重量
    items = [(v[i] / w[i], w[i]) for i in range(n)]
    # 按照单位重量价值从大到小排序
    items.sort(reverse=True)
    res = 0
    # 对每个物品进行分治
    for item in items:
        if c >= item[1]:
            c -= item[1]
            res += item[0] * item[1]
        else:
            res += item[0] * c
            break
    return res

其中，w是每个物品的重量，v是每个物品的价值，c是背包的容量。程序使用了元组来表示每个物品，元组的第一个元素是单位重量价值，第二个元素是重量。程序首先将物品按照单位重量价值从大到小排序，然后对每个物品进行分治，如果当前物品的重量小于等于背包的剩余容量，则全部放入背包，否则只能放入一部分，最终返回总价值。