01背包问题python

# 01背包问题的动态规划算法实现

# 物品数量
n = 5

# 背包容量
m = 10

# 物品重量和价值
w = [0, 2, 2, 6, 5, 4]
v = [0, 6, 3, 5, 4, 6]

# 初始化价值矩阵
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]

# 动态规划
for i in range(1, n + 1):
for j in range(1, m + 1):
if j < w[i]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

# 输出结果
print(dp[n][m])

相关问题

01背包问题Python

好的，我可以为您提供01背包问题的Python代码。以下是一个简单的实现：

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]

# 示例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)

print(knapsack(W, wt, val, n))  # 输出：220

该代码使用动态规划来解决01背包问题。在这个问题中，我们有一个固定的容量背包和一系列物品，每个物品有重量和价值两个参数。我们需要选择一些物品，使它们的总重量不超过背包容量，并且它们的总价值最大。

在代码中，`wt`和`val`分别是物品的重量和价值数组，`W`是背包容量，`n`是物品的数量。`dp`是一个二维数组，其中`dp[i][w]`表示在前`i`个物品中，当背包容量为`w`时，我们能够获得的最大价值。我们使用一个嵌套的循环来填充`dp`数组，最终返回`dp[n][W]`，即在前`n`个物品中，背包容量为`W`时能够获得的最大价值。

01背包问题python代码

下面是 01 背包问题的 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]


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

输出结果为 220。