0 1背包 算法

0-1背包表示每个物品只有取和不取的状态,即只能取0个或1个。 用子问题定义状态:即f[i][j]表示前i间物品恰放入一个容器为j的背包可以获得的最大价值。状态转移方程为: f[i][j] = max{f[i-1][j], f[i-1][j-weight[i]]+value[i]}