动态规划 0-1背包问题

原创

一点一线

发布于 2022-04-12 00:57:47

3020

发布于 2022-04-12 00:57:47

文章被收录于专栏：计算机技术计算机技术

动态规划在计算机算法中算是一类比较难的问题。这个问题的难点在于如何抽象出状态,根据状态抽象出状态转移方程。

动态规划中经典的问题是0-1背包问题，题目的很简单，有N个物品，每个物品的重量是Wi, 物品的价值是Vi，有一个容量为maxW的背包，问这个背包中能装下物品的最大价值是多少。

那就是对于每一个物品，有两个可能性，要么装进去，要么不装。可以分析一下这两种情况。

装进去： 1. 背包的剩余空间能装下该物品。 2. 装下该物品可以使背包的总价值增大（性价比高）。

不装： 1. 装不进去，剩余空间不够。 2. 剩余空间够，但是不能使背包的总价值增大（性价比不高）。

因此我们可以得到这样一个状态转移的方程：

dp[i][j] = max(dp[i-1][j], dp[i - 1][j - Wi] + Vi) 注意： j - Wi >= 0

dp 的行是物品的数量，列是背包的容量。这个方程就是上面解释的，满足条件，并且可以使背包的价值增大才能装下该物品。

看一下python实现的背包算法。

def package_problem(weight, value, max_weight):
    n = len(weight) + 1
    m = max_weight + 1
    dq = [[0 for j in range(m)] for i in range(n)]
    path = [-1] * (n - 1)
    for i in range(1, n):
        for j in range(m):
            if j - weight[i - 1] >= 0:
                dq[i][j] = max(dq[i-1][j], dq[i-1][j - weight[i - 1]] + value[i - 1])

    max_value = dq[len(weight)][max_weight]

    last = m-1
    for i in range(n-1, 0, -1):
        for j in range(last, 0, -1):
            if j - weight[i - 1] >= 0:
                if dq[i][j] == dq[i - 1][j - weight[i-1]] + value[i - 1]:
                    path[i - 1] = i - 1
                    last = j - weight[i-1]
                    break

    print(path)
    return max_value

if __name__ == '__main__':
    weight = [0,4, 1, 1,3]
    value = [0,3000,2000,1500,2000]
    max_weight = 5
    ret = package_problem(weight, value, max_weight)
    print(ret)

输出结果:

[-1, -1, 2, 3, 4]

5500

更多内容请关注： IT技术漫漫谈

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python