背包问题2（python解法）

刷题感悟：人生就像背包，前面的包选择好了，后面遇到更好的，那就是喜上加喜，不妨称之为连续性进步。 重要理论重述：要得到最终包能够容纳的价值量最高，那么一定实在体积都充分利用的情况下的。 🛹🛹背包问题，到底改选哪个包。🛹🛹

题目重述

在这里插入图片描述

代码实现

n,m = map(int,input().split())
f = [[0 for j in range(m+1)] for i in range(n+1)]

for i in range(1,n+1):
    w,v = map(int,input().split())
    for j in range(1,m+1):
        f[i][j] = f[i-1][j]
        if j>=w:
            f[i][j] = max(f[i][j],f[i][j-w]+v)
print(f[n][m])

算法实现的思路

我们不妨假设倒过来想，我们要得到最后的价值最大化，而最后一步选择的最大值是根据前面一步的最大值得来的。 举例说明： 一个人一次迈开5步到10步，那么只有每次迈开10步的时候，才能够得到最多的步数。而这里我们的小明的不同时刻的迈开的步数也发生了变化，但是总之，我们就是要去取到到每一步的最大值，然后去累加。

所以我们用j表示当前背包可以装下的容积，i表示可以装到的前面的i个道具。那么d[i][j]就表示为当背包的容量为j的前提下，可以装到前面的i个物品的最大价值量。那么后面的d[i+1][j]就会和d[i][j]以及d[i+1][j-w]有关。所以我们算法的设计就可以写成上面的形式。