python实现0-1背包

下面是 Python 实现 0-1 背包问题的代码：

def knapsack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
 
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 
    return K[n][W]
 
# 测试
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapsack(W, wt, val, n))  # 输出 220

这里的 knapsack 函数用于计算 0-1 背包问题的最大价值。W 是背包的最大容量，wt 和 val 分别是物品的重量和价值，n 是物品的数量。函数返回最大价值。

相关问题

用python实现 0-1背包问题

0-1背包问题是一种经典的动态规划问题，它的目标是从一组物品中选择一些物品，使得它们的总体积不超过背包的容量，同时总价值最大。下面是用Python实现0-1背包问题的代码：

def knapsack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
                
    return K[n][W]

其中，W表示背包的容量，wt表示物品的重量列表，val表示物品的价值列表，n表示物品的数量。函数返回的是能够放入背包的最大价值。

python实现0-1背包问题的递归,备忘录,及动态规划的比较

0-1背包问题是一个经典的动态规划问题，可以用递归、备忘录和动态规划三种方法来求解。

递归法：

递归法是最直观的方法，但是由于存在大量的重复计算，效率较低。递归方法的核心思想是将问题转化为规模更小的子问题逐步求解，最终得到原问题的解。

下面是递归方法的Python代码实现：

def knapsack_recursion(w, v, c, i):
    if i == 0 or c == 0:  # 背包容量为0或者物品数量为0时，价值为0
        return 0
    elif w[i] > c:  # 当前物品重量大于背包容量，不放入背包
        return knapsack_recursion(w, v, c, i-1)
    else:  # 取最大值：放入当前物品或者不放入当前物品
        return max(knapsack_recursion(w, v, c, i-1), v[i]+knapsack_recursion(w, v, c-w[i], i-1))

备忘录法：

为了避免递归方法中的重复计算，可以使用备忘录法。备忘录法的核心思想是在递归的过程中，将已经计算过的结果保存下来，下次需要用到时直接返回结果，避免重复计算。

下面是备忘录法的Python代码实现：

def knapsack_memorandum(w, v, c, i, memo):
    if memo[i][c] != -1:  # 如果已经计算过，直接返回结果
        return memo[i][c]
    if i == 0 or c == 0:
        memo[i][c] = 0
    elif w[i] > c:
        memo[i][c] = knapsack_memorandum(w, v, c, i-1, memo)
    else:
        memo[i][c] = max(knapsack_memorandum(w, v, c, i-1, memo), v[i]+knapsack_memorandum(w, v, c-w[i], i-1, memo))
    return memo[i][c]

动态规划法：

动态规划法是最优解的方法，它的核心思想是将问题划分为多个子问题，通过计算并保存子问题的结果，逐步推导出原问题的解。动态规划法通常采用二维数组来保存子问题的结果。

下面是动态规划法的Python代码实现：

def knapsack_dp(w, v, c, n):
    dp = [[0]*(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], v[i]+dp[i-1][j-w[i]])
    return dp[n][c]

以上三种方法的时间复杂度分别为：

- 递归法：$O(2^n)$
- 备忘录法：$O(nc)$
- 动态规划法：$O(nc)$

其中，$n$ 表示物品的数量，$c$ 表示背包的容量。可以发现，递归法的复杂度最高，备忘录法和动态规划法的复杂度相同，但是备忘录法需要额外的空间来保存结果。因此，动态规划法是最优解的方法。