感觉背包问题是dp中最好理解的了
定义:大小为i的背包最多能装的价值
转移方程 f(i)=max{f(i-w[j])+v[j]}
其中w[j]指的是第j件物品的重量，而v[j]指的是第j件物品的价值
代码实现(1)
for(int i=0;i<=m;i++)//容量 { for(int j=1;j<=n;j++)//物品的个数 { if(i-w[j]>=0)//如果能装下 { f[i]=max(f[i],f[i-w[j]]+v[j]);//装或者不装 } } }
代码实现(2)
for(int i=1;i<=n;i++)//这个还要更好理解些吧 { for(int j=w[i];j<=m;j++)//我们背包的容量至少都是物品的重量 { f[j]=max(f[j-w[i]]+v[i],f[j]); } }
原文：https://www.cnblogs.com/LJB666/p/10804752.html