<dp> 0--1背包问题

问题：

有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

例如：有一个容量为5的背包，有下面三个物品，问怎样才能让背包的放入最多价值的物品。

解题思路：

这是一个动态规划问题，看到这个问题，可能有人会想是否可以采用贪心算法，这样我们举几个例子就知道贪心算法并不正确。

正确思路：

定义：f(n,c)是考虑将n个物品放入容量为c的背包所能获得的最大的价值。

如果不放入第i个物品，那么：

f(i,c)= f(i-1,c)

如果放入第i个物品，那么：

f(i,c) = v(i) + f(i-1,c-w(i))

两种情况取最大的值，那么状态方程为:

f(i,c) = Max{f(i-1,c), v(i) + f(i-1,c-w(i))}