动态规划

背包问题作为NP完全问题，暂时不存在多项式时间算法。动态规划属于背包问题求解最优解的可行方法之一。此外，求解背包问题最优解还有搜索法等，近似解还有贪心法等，分数背包问题有最优贪心解等。 背包问题具有最优子结构和重叠子问题。动态规划一般用于求解背包问题中的整数背包问题（即每种物品所选的个数必须是整数）。 解整数背包问题： 设有${\displaystyle n}$件物品，每件价值记为${\displaystyle P_{i}}$，每件体积记为${\displaystyle V_{i}}$，用一个最大容积为${\displaystyle V_{\text{max}}}$的背包，求装入物品的最大价值。 用一个数组${\displaystyle f[i,v]}$表示取${\displaystyle i}$件商品填充一个容积为v的背包的最大价值，显然问题的解就是${\displaystyle f[n,V_{\text{max}}]}$。

${\displaystyle f[i,v]={\begin{cases}f[i-1,v],v<V_{i}\\\max\{f[i-1,v],f[i-1,v-V_{i}]+P_{i}\},v\geq V_{i}\\0,iv=0\\\end{cases}}}$

对于特例0 1背包问题（即每件物品最多放1件，否则不放入）的问题，状态转移方程：

${\displaystyle f[i,v]={\begin{cases}f[i-1,v],v<V_{i}\\\max\{f[i-1,v],f[i-1,v-V_{i}]+P_{i}\},v\geq V_{i}\\0,iv=0\\\end{cases}}}$

参考Pascal代码

for i:=1 to n do
  for v:=totv downto v[i] do
    f[v]:=max(f[v],f[v-v[i]]+p[i]);
writeln(f[totv]);

参考C++代码（不含include和数组声明）

#define max(x,y) (x)>(y)?(x):(y) //max宏函数，也可以自己寫或者使用algorithm
for(int i=1;i<=n;i++)
  for (v=totv;v>=v[i];v--)
    f[v]=max(f[v],f[v-v[i]]+p[i]);
printf("%d",f[totv]); //或std:cout<<f[totv];