7.01背包问题

问题描述

有4个物品，体积：2，3，4，5 。价值：3，4，5，6。背包容量：8。使用该背包装这些物品所能得到的最大价值。

思路

表示当前物品的编号，表示背包的剩余容量，表示当前物品的体积，表示物品的价值。分两种中情况讨论：

• 当前物品的体积大于背包的剩余体积
• 当前物品的体积小于等于背包的剩余体积
  通过构造物品编号与剩余体积的表可以求出最优解

代码

import prettytable as pt

if __name__ == "__main__":
    w = [0, 2, 3, 4, 5]  # 体积
    v = [0, 3, 4, 5, 6]  # 价值

    bag = 8

    table = [[0]*(bag+1) for i in range(len(w))]

    for i in range(1, len(table)):  # 编号
        for vol in range(1, len(table[0])):  # 剩余容量
            if w[i] > vol:  # 如果放不下
                table[i][vol] = table[i-1][vol]
            else:  # 如果能放下
                table[i][vol] = max(table[i-1][vol], table[i-1][vol-w[i]]+v[I])

    tb = pt.PrettyTable()
    for row in table:
        tb.add_row(row)
    print(tb)

结果