Python 01背包问题代码

可以参考以下代码：

def knapsack01(weights, values, capacity):
    n = len(weights)
    table = [[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]:
                table[i][j] = table[i-1][j]
            else:
                table[i][j] = max(table[i-1][j], table[i-1][j-weights[i-1]] + values[i-1])
    return table[n][capacity]

希望对你有所帮助！

相关问题

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编写背包问题代码

背包问题是一个经典的动态规划问题，可以用Python编写。以下是一个简单的实现：

def knapsack(values, weights, capacity):
    n = len(values)
    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 weights[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
    return dp[n][capacity]

其中，`values`和`weights`分别表示物品的价值和重量，`capacity`表示背包的容量。该函数返回能够放入背包的最大价值。

例如，假设有三个物品，其价值和重量分别为：

values = [60, 100, 120]
weights = [10, 20, 30]

背包容量为50，则最大价值为：

print(knapsack(values, weights, 50))  # 输出：220