01背包问题python

01背包问题是一个经典的动态规划问题，可以使用 Python 来实现。

假设有一个背包，它能装下的重量为 W，现在有 n 个物品，每个物品有重量和价值两个属性，要求从这 n 个物品中选择一些放入背包中，使得背包中物品的总重量不超过 W，同时总价值最大。

下面是一个 Python 实现：

def knapsack01(weights, values, W):
    # 初始化 dp 数组
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    # 动态规划
    for i in range(1, n + 1):
        for j in range(1, W + 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][W]

其中，weights 和 values 分别代表物品的重量和价值，W 代表背包的容量。

该算法的时间复杂度为 O(nW)，空间复杂度为 O(nW)。可以通过优化空间复杂度来减小空间开销。

相关问题

01背包问题Python

好的，下面是一个简单的 01 背包问题的 Python 代码示例：

def knapsack(W, wt, val, n):
    """
    :param W: 背包容量
    :param wt: 物品重量列表
    :param val: 物品价值列表
    :param n: 物品数量
    :return: 最大价值
    """
    # 初始化 dp 数组
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # 逐个考虑物品
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            # 如果当前物品重量大于背包容量，则无法放入该物品
            if wt[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            # 否则，比较放入和不放入该物品的价值，取较大值
            else:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], 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))  # 输出 220

以上就是一个简单的 01 背包问题的 Python 实现，希望对你有所帮助。

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。