动态规划基础-----01背包（总结）

1、动态规划（DP）

　　动态规划（Dynamic Programming，DP）与分治区别在于划分的⼦问题是有重叠的，解过程中对于重叠的部分只要求解⼀次，记录下结果，其他⼦问题直接使⽤即可，减少了重复计算过程。

　　另外，DP在求解⼀个问题最优解的时候，不是固定的计算合并某些⼦问题的解，⽽是根据各⼦问题的解的情况选择其中最优的。 　　动态规划求解具有以下的性质：

　　最优⼦结构性质、⼦问题重叠性质　　

　　最优⼦结构性质：最优解包含了其⼦问题的最优解，不是合并所有⼦问题的解，⽽是找最优的⼀条解线路，选择部分⼦最优解来达到最终的最优解。

　　⼦问题重叠性质：先计算⼦问题的解，再由⼦问题的解去构造问题的解（由于⼦问题存在重叠，把⼦问题解记录下来为下⼀步使⽤，这样就直接可以从备忘录中读取）。其中备忘录中先记录初始状态。

2、求解思路

　　①、将原问题分解为⼦问题（⼦问题和原问题形式相同，且⼦问题解求出就会被保存）； 　　②、确定状态：01背包中⼀个状态就是个物体中第个是否放⼊体积为背包中； 　　③、确定⼀些初始状态（边界状态）的值；

　　④、确定状态转移⽅程，如何从⼀个或多个已知状态求出另⼀个未知状态的值。（递推型）

3、01背包问题求解思路

　　①、确认⼦问题和状态

　　01背包问题需要求解的就是，为了体积V的背包中物体总价值最⼤化，件物品中第件应该放⼊背包中吗？（其中每个物品最多只能放⼀件）

　　为此，我们定义⼀个⼆维数组，其中每个元素代表⼀个状态，即前个物体中若⼲个放⼊体积为背包中最⼤价值。数组为：，其中表⽰前件中若⼲个物品放⼊体积为的背包中的最⼤价值。

　　②、初始状态

　　初始状态为和都为0，前者表⽰前0个物品（也就是空物品）⽆论装⼊多⼤的包中总价值都为0，后者表⽰体积为0的背包啥价值的物品都装不进去。 我⾃⼰写的的没保存，只能把这个整来凑数了伪代码

for(int t=1;t<=n;t++){

for(int j=V;j>=v[t];j--)

{

dp[j]=max(dp[j],dp[j-v[t]]+w[t]); }}