动态规划---01背包问题

01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多

01背包的状态转换方程

 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ),  f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中,可以取得的最大价值。

Pi表示第i件物品的价值。

决策:为了背包中物品总价值最大化,第 i件物品应该放入背包中吗 ?

图表的生成顺序是从左到右、从上到下,但是列表中物品的顺序是没有关系的。

image.png

在线01背包问题解决:http://karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×