01背包问题:
01背包其实是一个递推问题,每次都是最优解不断推出最终结果。一维和二维都要掌握。
动态方程:
F[ i , v ] = max { F[ i−1 , v ] , F[ i−1 , v−Ci ] + Wi } ,意思是:当选第 i 个物品时 F [ i-1 , v ] 代表不放第 i 件物品,F [ i-1 , v - Ci ] + Wi ; 代表放第 i 件物品,第 i-1 件物品得到的最优解加上第 i 件物品的价值。可以用一维数组 F[ i ] = max (F[ i ] ,F[ i - ci ]+wi ) ;
代码(二维数组):
memset(dp,0,sizeof(dp)) ;
for(int i=1 ;i<=n ;i++)......
阅读全文