动态规划

0-1背包

问题描述：给定n个以(w,v)表示的物品,其中w代表重量,v代表价值;此外,给定一个背包的总重量W. 问:能获得的最大价值为几何?

解：对于每个物品v，可以选择选或者不选。只要比较一下选和不选哪个带来的价值更高即可。

if w[i]>背包承重j,无法入包: 
F[i][j]=F[i-1][j]; 
else 
F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+v[i]); 

for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            if(j < w[i])    dp[i][j]  = dp[i-1][j];
            else dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
        }
    }