动态规划(Dynamicprogramming)背包问题资源分配问题生产计划问题复合系统工作可靠性问题有一个徒步旅行者,其可携带物品重量的限度为a公斤,设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值(作用),问此人应如何选择携带的物品(各几件),使所起作用(使用价值)最大?物品12…j…n重量(公斤/件)a1a2…aj…an每件使用价值c1c2…这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。背包问题设xj为第j种物品的装件数(非负整数)则问题的数学模型如下:用动态规划方法求解,令fk(y)=总重量不超过y公斤,包中只装有前k种物品时的最大使用价值。其中y≥0,k=1,2,…,n。所以问题就是求fn(a)其递推关系式为:当k=1时,有:例题:求下面背包问题的最优解物品123重量(公斤)325使用价值8512解:a=5,问题是求f3(5)所以,最优解为X=(),最优值为Z=13。
运筹学动态规划 来自淘豆网m.daumloan.com转载请标明出处.
