动态计划的基本思想:
动态计划算法一般用于求解具有某种最优性子的题目,即我们寻常所说的最优子构造性子。
动态计划算法与分治法相似,其基本思想也是将待求解题目剖析成多少个子题目,先求解子题目,然后从这些子题目的解获得原题目的解。与分治法最大的区别是,适合于用动态计划求解的题目,经剖析获得子题目每每不是相互自力的,即下一个子阶段的求解是建立在上一个子阶段的解的基础上,举行进一步的求解。
若用分治法来解这类题目,则剖析获得的子题目数量太多,有些子题目被反复盘算了很屡次。假如我们能够保留已处理的子题目的答案,而在须要时再找出已求得的答案,如许就能够防止大批的反复盘算,节省时间。我们能够用一个表来纪录一切已解的子题目的答案。不论该子题目今后是不是被用到,只需它被盘算过,就将其效果填入表中。
题目形貌:
给定N中物品和一个背包。物品i的分量是Wi,其代价位Vi ,背包的容量为C。问应当怎样挑选装入背包的物品,使得转入背包的物品的总代价为最大??
在挑选物品的时刻,对每种物品i只要两种挑选,即装入背包或不装入背包。不能讲物品i装入屡次,也不能只装入物品的一部分。因而,该题目被称为0-1背包题目。
题目剖析:令V(i,j)示意在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大代价,则能够获得以下的动态计划函数:
(1) V(i,0)=V(0,j)=0 (2) (a) V(i,j)=V(i-1,j) j<wi (b) V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式表明:假如第i个物品的分量大于背包的容量,则装人前i个物品获得的最大代价和装入前i-1个物品获得的最大价是雷同的,即物品i不能装入背包。
(2)式表明:假如第i个物品的分量小于背包的容量,则会有一下两种状况:(a)假如第i个物品没有装入背包,则背包中物品代价就即是把前i-1个物品装入容量为j的背包中所获得的代价。(b)假如把第i个物品装入背包,则背包物品的代价即是第i-1个物品装入容量位j-wi 的背包中的代价加上第i个物品的代价vi; 明显,取两者中代价最大的作为把前i个物品装入容量为j的背包中的最优解。
引荐教程:PHP教程
以上就是01背包题目动态计划的细致内容,更多请关注ki4网别的相干文章!