编写程序实现背包问题。 问题描述为：设有编号为1、2、....、n的n个物品，它们的重量分别为W1,W2,...,Wn，价值分别为V1,V2,...,Vn，其中Wi、Vi给（1≤i≤n）均为正数，有一个背包可以携带的最大重量不超过W。求在不超过背包负重的前提下，使背包装入的总价值最大。具体如下 对于下表一个背包问题，n=5，设背包容量W=100 i 1 2 3 4 5 wi 10 20 30 40 50 vi 20 30 66 40 60 vi/wi 2.0 1.5 2.2 1.0 1.2

以下是使用动态规划的方式实现背包问题的 Python 代码，注释中有详细的解释：

def knapsack(n, W, weights, values):
    # 初始化一个二维列表，用于存储状态转移方程
    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    # 对于前 i 个物品和容量为 j 的背包，可以考虑选择放或不放第 i 个物品
    for i in range(1, n + 1):
        for j in range(1, W + 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]

    # 返回最终的状态值，即在不超过背包重量的前提下，背包所能装载的最大价值
    return dp[n][W]

# 测试
n = 5
W = 100
weights = [10, 20, 30, 40, 50]
values = [20, 30, 66, 40, 60]
print(knapsack(n, W, weights, values))  # 输出：146

这个算法的时间复杂度为 $O(nW)$，其中 $n$ 是物品数量，$W$ 是背包最大容量。