动态计划的基本思想：
动态计划算法一般用于求解具有某种最优性子的题目，即我们寻常所说的最优子构造性子。
动态计划算法与分治法相似，其基本思想也是将待求解题目剖析成多少个子题目，先求解子题目，然后从这些子题目的解获得原题目的解。与分治法最大的区别是，适合于用动态计划求解的题目，经剖析获得子题目每每不是相互自力的，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，举行进一步的求解。
若用分治法来解这类题目，则剖析获得的子题目数量太多，有些子题目被反复盘算了很屡次。假如我们能够保留已处理的子题目的答案，而在须要时再找出已求得的答案，如许就能够防止大批的反复盘算，节省时间。我们能够用一个表来纪录一切已解的子题目的答案。不论该子题目今后是不是被用到，只需它被盘算过，就将其效果填入表中。
题目形貌：
给定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网别的相干文章！
