写一段代码解决背包问题

背包问题是一个经典的动态规划问题，其基本思路是将问题分解成子问题，然后通过求解子问题最优解来推导出原问题的最优解。

下面是一个使用动态规划求解背包问题的 Python 代码示例：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

其中，`weights` 和 `values` 分别表示物品的重量和价值，`capacity` 表示背包的容量。`dp` 是一个二维数组，`dp[i][j]` 表示前 i 个物品在容量为 j 的背包中能够获得的最大价值。

在代码中，我们使用两层循环来遍历 `dp` 数组，然后根据当前物品的重量和价值以及背包的容量来更新 `dp` 数组中的值。最终返回 `dp[n][capacity]` 即可得到最优解。

需要注意的是，这里的时间复杂度为 O(n * capacity)，空间复杂度也为 O(n * capacity)，因此在实际应用中可能需要进行优化。