0-1背包问题贪心算法python·

0-1背包问题是一个经典的组合优化问题，贪心算法是其中一种解决方法。下面是一个基于单位价值量的贪心算法的Python实现：

def fractional_knapsack(value, weight, capacity):
    """Return maximum value of items and their fractional amounts.
 
    (max_value, fractions) is returned where max_value is the maximum value of
    items with total weight not more than capacity.
    fractions is a list where fractions[i] is the fraction that should be taken
    of item i, where 0 <= i < total number of items.
 
    value[i] is the value of item i and weight[i] is the weight of item i
    for 0 <= i < n where n is the number of items.
 
    capacity is the maximum weight.
    """
    index = list(range(len(value)))
    # item index list
    ratio = [v/w for v, w in zip(value, weight)]
    # calculate unit value of each item
    index.sort(key=lambda i: ratio[i], reverse=True)
    # sort item index in descending order of unit value
    max_value = 0
    fractions = [0]*len(value)
    for i in index:
        if weight[i] <= capacity:
            fractions[i] = 1
            max_value += value[i]
            capacity -= weight[i]
        else:
            fractions[i] = capacity/weight[i]
            max_value += value[i]*capacity/weight[i]
            break
    return max_value, fractions

其中，value和weight分别是物品的价值和重量，capacity是背包的容量。函数返回最大价值和每个物品的分数，以便计算每个物品的实际数量。