背包问题递归、备忘录、动态规划Python实现

背包问题是一个经典的动态规划问题，其主要思想是在给定的物品中选择一些物品放入一个容量为W的背包中，使得背包中物品的价值总和最大。

以下是递归、备忘录、动态规划三种实现方法的Python代码。

递归实现：

def knapsack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0

    if wt[n-1] > W:
        return knapsack(W, wt, val, n-1)

    else:
        return max(val[n-1] + knapsack(W-wt[n-1], wt, val, n-1), knapsack(W, wt, val, n-1))

备忘录实现：

def knapsack(W, wt, val, n, memo):
    if n == 0 or W == 0:
        return 0

    if memo[n-1][W-1] != -1:
        return memo[n-1][W-1]

    if wt[n-1] > W:
        memo[n-1][W-1] = knapsack(W, wt, val, n-1, memo)
        return memo[n-1][W-1]

    else:
        memo[n-1][W-1] = max(val[n-1] + knapsack(W-wt[n-1], wt, val, n-1, memo), knapsack(W, wt, val, n-1, memo))
        return memo[n-1][W-1]

W = 50
wt = [10, 20, 30]
val = [60, 100, 120]
n = len(val)
memo = [[-1 for i in range(W)] for j in range(n)]
print(knapsack(W, wt, val, n, memo))

动态规划实现：

def knapsack(W, wt, val, n):
    dp = [[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:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

W = 50
wt = [10, 20, 30]
val = [60, 100, 120]
n = len(val)
print(knapsack(W, wt, val, n))