贪心算法求解背包问题代码

以下是一种用贪心算法解决背包问题的代码示例（使用 Python 语言）：

def knapsack(items, maxweight):
    """
    Solve the knapsack problem by finding the most valuable
    subsequence of `items` subject that weighs no more than
    `maxweight`.

    `items` is a list of pairs `(value, weight)`, where `value` is
    a number and `weight` is a non-negative integer.

    `maxweight` is a non-negative integer.

    Returns a pair whose first element is the sum of values in the most
    valuable subsequence, and whose second element is the subsequence.
    """
    # Order items by value-to-weight ratio
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
    knapsack = []
    total_value = 0
    total_weight = 0
    for value, weight in items:
        if total_weight + weight <= maxweight:
            knapsack.append((value, weight))
            total_value += value
            total_weight += weight
    return total_value, knapsack

# Example usage
items = [(4, 12), (2, 1), (6, 4), (1, 1), (2, 2)]
maxweight = 15
value, knapsack = knapsack(items, maxweight)
print("The maximum value of items in the knapsack is", value)
print("The items in the knapsack are", knapsack)

该代码使用贪心策略，将物品按照价值-重量比从高到低排序，依次选取能放入背包中的物品。最终得到背包中物品的最大价值和物品组成。