[数据结构与算法]01背包问题（python）

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

解题思路

1.先将输入的第一行中物品的数量和背包的总体积取出

# 取得物品的个数和背包的总体积
a = [int(i) for i in input().split()]
# 物品的个数
n = a[0]
# 背包总体积
m = a[1]

2.将给出的各个物品的体积和质量分别用两个列表分别存入

# 从键盘输入中得到物品的体积和价值
def qu(N):
    for i in range(N):
        x = [int(j) for j in input().split()]
        v.append(x[0])
        w.append(x[1])
    return v, w



# 各个物品的体积列表
v = []
# 对应物品的价值
w = []
# 将物品的体积和价值装入列表中
qu(n)

3.最重要的一步，即利用动态规划将背包各个时期的最优解解出来，最后填写一个过程的列表。

（1）先建立一个二维数组，行从0开始到物品数量结束，列从0开始一直到背包的总体积

# 模拟背包
f = [[0] * (m + 1) for _ in range(n + 1)]

（2）从第一行开始，?如果包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即f[i][j] = f[i - 1][j]；如果还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i - 1]] + w[i-1])；

# 获取最大的价值
def max_():
    for i in range(1, n+1):  # 有几个物品可供选择
        for j in range(1, m + 1):  # 模拟背包容量从m+1
            if j < v[i-1]:  # 如果此时背包容量小于当前物品重量
                f[i][j] = f[i - 1][j]  # 不拿这个物品
            else:
                # 此时有两种选择,拿或不拿
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i - 1]] + w[i-1])
                # 选择最好的一种方式，也就是两种情况作比较，取价值的较大值

（3）此时就会形成一个二维的列表具体列表如下

（4）上面二维表格中最右下角即为最大价值

总的代码

# 从键盘输入中得到物品的体积和价值
def qu(N):
    for i in range(N):
        x = [int(j) for j in input().split()]
        v.append(x[0])
        w.append(x[1])
    return v, w


# 获取最大的价值
def max_():
    for i in range(1, n+1):  # 有几个物品可供选择
        for j in range(1, m + 1):  # 模拟背包容量从m+1
            if j < v[i-1]:  # 如果此时背包容量小于当前物品重量
                f[i][j] = f[i - 1][j]  # 不拿这个物品
            else:
                # 此时有两种选择,拿或不拿
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i - 1]] + w[i-1])
                # 选择最好的一种方式，也就是两种情况作比较，取价值的较大值


# 取得物品的个数和背包的总体积
a = [int(i) for i in input().split()]
# 物品的个数
n = a[0]
# 背包总体积
m = a[1]
# 各个物品的体积列表
v = []
# 对应物品的价值
w = []
# 将物品的体积和价值装入列表中
qu(n)
# 模拟背包
f = [[0] * (m + 1) for _ in range(n + 1)]
# 获取最大的价值
max_()
print(f[n][m])