0到1背包问题Python代码实现

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

def knapsack_01(W, wt, val, n):
    # 创建dp数组，用于存储最大价值
    dp = [[0 for x in range(W + 1)] for y in range(n + 1)]
 
    # 递推填充dp数组
    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是背包的容量，wt是物品的重量数组，val是物品的价值数组，n是物品的数量。

相关问题

完全背包问题python代码实现

以下是使用动态规划思想实现的完全背包问题的Python代码：

def knapsack(W, wt, val, n):
    dp = [0] * (W + 1)
    for i in range(1, W + 1):
        for j in range(n):
            if wt[j] <= i:
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])
    return dp[W]

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

在主函数中，我们定义了背包容量W，物品重量wt，物品价值val和物品数量n。我们调用knapsack函数来求解完全背包问题。该函数使用动态规划实现。它创建一个长度为W + 1的列表dp，初始化为全0。然后，我们在0到W的范围内迭代，同时迭代物品列表中的所有物品。如果物品的重量小于等于i，我们就可以将物品放入背包中。我们使用dp[i - wt[j]] + val[j]计算放置当前物品后得到的总价值。最后，我们返回dp[W]，它储存了背包最大价值。

0-1背包python代码实现

好的，以下是一个简单的0-1背包问题的Python代码实现：

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]

希望可以帮到你！请问您还有其他问题吗？