01背包 最基本的思路

对于背包问题，通常的处理方法是搜索。
用递归来完成搜索，算法设计如下：
int Make(int i /*处理到第i件物品*/ , int j/*剩余的空间为j*/) 初始时i=m , j=背包总容量
{
if(i=0)
return 0;
if(j>=wi) (背包剩余空间可以放下物品 i )
{r1=Make(i-1,j-wi)+v; (第i件物品放入所能得到的价值 )
r2:=Make(i-1,j); (第i件物品不放所能得到的价值 )
Make(r1>r2?r1:r2);
}
}
这个算法的时间复杂度是O(2^n)

做点题就明白了，这方面的题不少。
f[i][j] = max{f[i-1][j], f[i-1][j-w[i]]+v[i]}
到达一个状态，只能从两个状态而来，也就是取和不取的状态。
我在前i件物品取得重量不超过j的最大价值，是由取不取第i件物品而得到的
这个是比较基本的思想，比较好懂的。
看看算法导论吧，很有帮助

（-_-!竟然有人说搜索...无语