编辑代码

def knapsack_fruits(weights, values, capacity):
    n = len(weights)
    dp = [[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:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
            else:
                dp[i][j] = dp[i-1][j]

    # 打印装包策略
    print_knapsack_strategy(dp, weights, values, capacity)

    return dp[n][capacity]

def print_knapsack_strategy(dp, weights, values, capacity):
    i, j = len(dp) - 1, len(dp[0]) - 1
    selected_items = []

    while i > 0 and j > 0:
        if dp[i][j] != dp[i-1][j]:
            selected_items.append(i - 1)
            j -= weights[i-1]
        i -= 1

    print("装入水果的策略：")
    for idx in reversed(selected_items):
        print(f"{idx + 1}. {weights[idx]}kg的{values[idx]}元水果")

def main():
    weights = [15, 18, 10, 9]
    values = [300, 180, 150, 270]
    capacity = 20

    max_value = knapsack_fruits(weights, values, capacity)
    print(f"背包中装入水果的最大总价值为: {max_value}元")

if __name__ == "__main__":
    main()