python 解决0-1背包问题算法完整代码

2022-03-11 00:00:00 python 解决

问题：给定一个载重量为m的背包，以及n个重量为wi、价值为pi的物体，1<=i<=n，要求把物体装入背包，使背包内的物体价值最大，把这类问题称为背包问题。通常称物体不可分割的背包问题为0/1背包问题。
这个问题也可以用动态规划的分阶段决策方法，来确定把哪一个物体装入背包的最优决策。类似于资源分配那样，令optp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值，j=1,2,…,m。可以得到下面的动态规划函数：
optp[i][0] = optp[0][j] = 0………………………………………..(1)
optp[i][j] = optp[i - 1][j] (j < wi)…………………………………(2)
optp[i][j] = max{optp[i - 1][j], optp[I - 1][j - wi] + pi}(j >= wi)…(3)
式(1)表示，把前面i物体装入载重量为0的背包，或者把0个物体装入载重量为j的背包，得到的价值都为0。（2）式表明，如果第i个物体的重量大于背包的载重量，则装入前面i个物体得到的最大价值，与装入前面i – 1个物体得到的最大价值一样（第i个物体没有装入背包）。式（3）表明，当第i个物体的重量小于背包的载重量时，如果把第i个物体装入载重量为j的背包后总价值上升，那么就装入，否则不装入。

"""
皮蛋编程(https://www.pidancode.com)
创建日期：2022/4/1
功能描述：python 解决0-1背包问题算法完整代码
"""

# n个物体的重量(w[0]无用)
w = [0, 2, 2, 6, 5, 4]
# n个物体的价值(p[0]无用)
p = [0, 6, 3, 5, 4, 6]
# 计算n的个数
n = len(w) - 1
# 背包的载重量
m = 10
# 装入背包的物体，元素为True时，对应物体被装入(x[0]无用)
x = [False for raw in range(n + 1)]
v = 0
# optp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值
optp = [[0 for col in range(m + 1)] for raw in range(n + 1)]


def knapsack_dynamic(w, p, n, m, x):
    # 计算optp[i][j]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            optp[i][j] = optp[i - 1][j]
            if (j >= w[i]) and (optp[i - 1][j - w[i]] + p[i] > optp[i - 1][j]):
                optp[i][j] = optp[i - 1][j - w[i]] + p[i]
    # 递推装入背包的物体
    j = m
    for i in range(n, 0, -1):
        if optp[i][j] > optp[i - 1][j]:
            x[i] = True
            j = j - w[i]
            # 返回最大价值
    v = optp[n][m]
    return v


print('最大值为：' + str(knapsack_dynamic(w, p, n, m, x)))
print(x[1:])

输出：
最大值为：15
[True, True, False, False, True]

代码在python3.9下测试通过

相关文章