用python实现背包问题

以下是使用Python实现背包问题的示例代码，其中包括贪心算法和动态规划算法两种方法：

1.贪心算法

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 value per unit weight
    ratio = [v/w for v, w in zip(value, weight)]
    # index sorted by ratio in decreasing order
    index.sort(key=lambda i: ratio[i], reverse=True)

    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

2.动态规划算法

def knapsack_dynamic_programming(weights, values, capacity):
    n = len(weights)
    # initialize the matrix with zeros
    matrix = [[0]*(capacity+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, capacity+1):
            if weights[i-1] > j:
                matrix[i][j] = matrix[i-1][j]
            else:
                matrix[i][j] = max(matrix[i-1][j], values[i-1] + matrix[i-1][j-weights[i-1]])

    # determine which items to pick
    picks = []
    w = capacity
    for i in range(n, 0, -1):
        if matrix[i][w] != matrix[i-1][w]:
            picks.append(i-1)
            w -= weights[i-1]

    picks.reverse()

    return matrix[n][capacity], picks