Python实现01背包问题代码

当然可以，以下是Python实现01背包问题的代码：

def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0 for j in range(capacity+1)] for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, capacity+1):
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][capacity]

希望对你有帮助！

相关问题

Python写01背包问题代码贪心算法

好的，以下是Python实现01背包问题的贪心算法代码：

def fractional_knapsack(value, weight, capacity):
"""Return maximum value of items and their fractional amounts.

(max_value, [0/1, ...]) is returned where max_value is the maximum value of
items with total weight not more than capacity.

value[i]/weight[i] is the value per unit of weight of item i.

capacity is the maximum weight.

weight must be a list of integers.

value must be a list of integers.

capacity must be an int.
"""
index = list(range(len(value)))
# get value per unit weight in list
ratio = [v/w for v, w in zip(value, weight)]
# index is sorted according to value per unit weight in decreasing order
index.sort(key=lambda i: ratio[i], reverse=True)

max_value = 0
fractions = [0]*len(value)
for i in index:
if weight[i] <= capacity:
fractions[i] = 1
max_value += value[i]
capacity -= weight[i]
else:
fractions[i] = capacity/weight[i]
max_value += value[i]*capacity/weight[i]
break

return max_value, fractions

请问是否还有其他问题需要回答呢？

用python写01背包问题的代码

以下是 Python 实现 01 背包问题的代码：

def knapsack01(W, wt, val, n):
    """
    W: 背包容量
    wt: 物品重量列表
    val: 物品价值列表
    n: 物品数量
    """
    # 使用二维数组 dp[i][j] 记录前 i 个物品中，容量为 j 的背包所能获得的最大价值
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    
    # 递推计算 dp 数组
    for i in range(1, n+1):
        for j in range(1, W+1):
            if j < wt[i-1]:  # 当前背包容量不足以放下物品 i
                dp[i][j] = dp[i-1][j]
            else:  # 当前背包容量可以放下物品 i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1])
    
    # 返回最大价值
    return dp[n][W]

# 示例
W = 10
wt = [2, 3, 4, 5]
val = [3, 4, 5, 6]
n = len(wt)
print(knapsack01(W, wt, val, n))  # 输出 10

在上述代码中，我们使用二维数组 `dp` 来记录前 `i` 个物品中，容量为 `j` 的背包所能获得的最大价值。具体来说，`dp[i][j]` 表示前 `i` 个物品中，容量为 `j` 的背包所能获得的最大价值。

接着，我们使用两个循环来递推计算 `dp` 数组。在循环中，我们通过比较将当前物品放入背包和不放入背包两种情况的价值，来确定背包的最大价值。

最后，我们返回 `dp[n][W]`，即前 `n` 个物品中，容量为 `W` 的背包所能获得的最大价值。