试用动态规划方法求解0-1背包问题并编程在计算机上实现，同时进行时间复杂性分析。 n个物品和1个背包，对物品i，其价值为vi，重量为wi，背包的容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大。

0-1背包问题是一个经典的动态规划问题，其状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)

其中，dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值，wi 和 vi 分别为第 i 个物品的重量和价值。

时间复杂度分析：

该算法的时间复杂度为 O(nW)，其中 n 为物品数，W 为背包容量。因为需要填满一个 n*W 的二维数组，每个位置需要计算一次状态转移方程。

下面是 Python 的代码实现：

def knapsack(n, W, wt, val):
    # 初始化二维数组
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    
    # 填充二维数组
    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if j - wt[i-1] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    
    # 返回最大价值
    return dp[n][W]

调用方式如下：

n = 4
W = 5
wt = [2, 1, 3, 2]
val = [12, 10, 20, 15]

print(knapsack(n, W, wt, val))  # 输出：37

该算法的空间复杂度为 O(nW)，因为需要填满一个 n*W 的二维数组。