python实现背包问题

背包问题是一个经典的动态规划问题，Python可以很方便地实现。具体实现步骤如下：
1. 定义一个二维数组dp，其中dp[i][j]表示在前i个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值。
2. 初始化dp数组，将dp[j]和dp[i]均赋值为0。
3. 遍历物品列表，对于每个物品i，遍历背包容量j，如果当前物品的重量大于背包容量j，则dp[i][j] = dp[i-1][j]，即当前物品不能放入背包中，最大价值不变；否则，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，即当前物品可以放入背包中，最大价值为前i-1个物品放入容量为j的背包中所能获得的最大价值和当前物品的价值之和。
4. 遍历完所有物品后，dp[-1][-1]即为所求的最大价值。
下面是Python代码实现背包问题：

# 0/1背包问题
def knapsack01(n, c, w, v):
    dp = [[0 for j in range(c+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, c+1):
            if w[i] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
    return dp[-1][-1]