01背包[学术]

对于01背包在上次的文章中已经提到过，但这一次将要系统的学习它。

01背包问题：

有 N件物品和一个容量为 M的背包。第 i件物品的重量是wi ，价值是Di 。求解将哪些物品装入背 包可使这些物品的重量总和不超过背包容量，且价值总和最大。

在上述例题中，每个物品有不拿和拿两种情况，对应二进制中的0和1，我们将这类问题统称为『01背 包』问题。

我们已知条件有第 i个物品的重量 Wi和他的价值Di ，以及背包的容量 。 

按照dp五步法来解：

1.构造问题:

题意即问题

2.拆解成若干个子问题：

我们设f[i][j]是前1到i的物品，重量为j背包价值的最优解。

3.求解子问题：

有了2的铺垫可以考虑如何设计动态转移方程，假设当我们计算到i时，前i-1个物品都已经计算完了，那么此时便有了两种决策（选择）分别是：1.不将第i件物品加入到背包中，那么这种情况下dp[i][j]=dp[i-1][j]；2.如果将第i件物品放入背包中那么此情况下的最优解就是dp[i][j]=dp[i-1][j-wi]+Di

4.根据已知子问题求解大问题

dp[i][j]=max(dp[i-1][j]，dp[i-1][j-wi]+Di)

5.判断复杂度

时间复杂度O(nm) 空间复杂度O(nm)

code自己写去