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]);
}
}