背包算法动态规划

❶ 用动态规划算法怎样求解01背包问题

动态规划主要解决的是多阶段的决策问题。

01背包中，状态为背包剩余的容量，阶段是每一个物品，决策是是否选择当前的物品。

所以用动态规划来解决是非常贴切的。

我们设f[V]表示已经使用容量为V时所能获得的最大价值，w[i]表示i物品的质量，c[i]表示i物品的价值。

for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);

这便是所谓的一个状态转移方程。

f[j]表示在已经使用容量为j时的最大价值，f[j-w[i]]表示在已经使用容量为j-w[i]时的最大价值。

f[j]可以由f[j-w[i]]这个状态转移到达，表示选取w[i]这个物品，并从而获得价值为c[i]。

而每次f[j]会在选与不选中决策选出最优的方案。

从每一个物品，也就是每一个阶段的局部最优推出最后的全局最优值。这样就解决了01背包问题