基于动态规划方法求解0-1背包等问题1 .主题n件物品和一个背包。 对于物品I，将其价值设为vi，重量设为wi，背包容量设为w。 你怎么选择行李放在背包里，使放在背包里的行李总价值最大？ 其中，wi，w都是正整数。
2 .分析首先，要明确背包容量的变化对装行李总数有一定的限制关系，往往n件行李不一定能装在背包里(只要能装，都装的时候一定价值最大)。
其次，根据贪婪算法，需要明确的是求解是局部最优的
1 .最有价值的东西放进背包
2 .最轻的放在背包里
3 .价值与重量之比最大的放在背包里
任何一个都不一定能得到最佳的结果，因为可能有背包容量物品的总重量，有时几乎是最佳解。
现在需要考虑的是全局最好的
第一种方法是暴力地列出物品满足要求的所有数组组合，找出其价值最大的情况，但由于这种方法很复杂，所以这次不讨论。
第二种方法是采用动态规划，这种方法基于分治的思想，但与分治不同
具体而言，它位于动态规划的三个基本要素。
1 .最佳子结构性质
一个问题的最优解可以有效地从子问题的最优解中构造出来，保证了原问题的最优解可以从子问题的最优解中导出，是动态规划的基础。 基于最优子结构推导递推公式或动态规划基本方程是解决所有动态规划问题的基本方法。
2.子问题重叠性质
由于在求解过程中几个子问题多次出现并重叠，所以如果是初次遇到就解决并保存，如果是再次遇到就不重复计算而直接查表得到，从而提高求解效率。 请注意，此性质不是必需条件，也不是动态规划的核心。 但是，如果没有这种形式，这种方法就没有优点(如果没有重叠的子问题，使用直接分治解就可以了)。
3.自底向上的求解方法
考虑到子问题重叠的性质，采用自下而上的方法，首先填写停止条件，求解并保存各级子问题，直到得到原问题的解。
背包问题可以描述为几个有序阶段，每个阶段的状态只与前一阶段的状态有关，是一个多阶段的动态规划问题
动态规划可以使用递归或递归写法实现。 其中递归的方法有时被称为记忆化检索。
动态规划的两种实现方法：
备忘录的自上而下法
(自然递归地编写过程，通常用数组保存部分问题的解) )在特殊情况下，实际上并不是递归地考察所有的部分问题。 自下而上法
(需要适当定义子问题规模的概念，并按从大到小的顺序求解)由于没有频繁调用递归函数的开销，时间复杂度函数通常具有较小的系数。 背包问题可以描述为几个有序阶段，每个阶段的状态只与前一阶段的状态有关，是一个多阶段的动态规划问题
动态规划可以使用递归或递归写法实现。 其中递归的方法有时被称为记忆化检索。
动态规划的求解步骤：
1 .判断是否具有最佳亚结构性质，考察是否适合该方法
2 .由底向上，以最小问题为分界点向上求解
3 .递归定义最佳值，包括停止条件和递归公式
4 .充分利用子问题重叠的性质
贪心与动态规划：
贪婪和动态规划要求最适合原始问题的子结构。 但是贪婪法并不是在子问题解决后再选择使用哪一个，而是用一个策略直接选择子问题进行求解，从而舍弃没有选择的子问题，直接根据当前的选择继续进行选择。 动态规划考虑所有子问题，寻找整体最优。 贪婪法只是单链选择局部最好。
分治法与动态规划：
由于动态规划基于分治的思想和冗余的解决，动态规划中各子问题可以重复，但分治法中各子问题是独立的。 分治法解决的问题不一定是优化问题，动态规划解决的一定是优化问题。
3 .算法设计和二维码数组w[n]存放物品的重量
储存数组v[n]件物品的价值
w :背包的重量
数组C[n 1][W 1] :存储每次反复执行结果，C[i][j]是C[n][W]子问题的最优解，表示放入前I个，且背包容量为j时装货物的最大价值。
数组x[n] :存放背包物品的状态
该问题满足动态规划的最优解条件(具体内容在总结中)，并运用动态规划的思想进行求解。 将问题分为多个子问题，各物品可以选择是否放入背包。 首先，判断当前物品的重量是否大于背包能容纳的重量； 如果该物体能够被容纳，则判断放入该物体C[i1][j-w[i]] v[i]的一方得到的价值高，还是不放入该物体C[i1][j]的一方得到的物品的总价值高。
C[i][j]表示放入的东西在最初的I个以内，背包容量为j时放入的东西的最大价值，问题C[n][w]是最终解决的问题。
如果只考虑第I个物品的求解方案(放还是不放)，就可以变换为关于第i-1个物品的问题。
装：第一个i-1件物品放入容量为j-w[i]的背包。 此时，得到最大价值为C[i-1][j-w[i]] v[i]
进不去：前i-1件物品放在容量为j的背包里，此时得到的最大价值等于C[i-1][j]
knapsack_01(w，v，w ) for i=1 to n do C[i][0]=0//背包剩余容量为0时，装物品的最大价格
值为0for j=1 to w do C[0][j]=0//物品为0时，装入物品最大价值为0for i = 1 to n for j = 1 to w if j < w [i]//背包剩余容量不够 then C[i][j]=C[i-1][j]//装不了第i个物品，不装入 else then C[i][j]=max{C[i-1][j],C[i-1][j-w[i]]+v[i]}//在不装入该物品和装入该物品中间选择较大值return CTRACEBACK-01(w, W, C) //x[1..n]为构建的最优解 Let x[0..n]be a new arrayn = w.length j = W //remaining capacity剩余容量for i = n to 1 do if C[i][j] == C[i-1][j] then//如果装前n个物品价值最大值=装前n-1个物品价值最大值 x[i] = 0 //没装第n个物品 else x[i] = 1 //装了第n个物品 j -= w[i] //update capacity更新容量，减去放第i件物品容量return x易混：
C[i-1][j-w[i]]+v[i] //表明单纯是用容量换了新增加一个物品的代价，此时一定是相对于上一个状态的最优解
如果取第i件物品放入背包，则背包容量还剩j-w[i],所以要取前i-1件物品放入背包剩余容量j-w[i]所获得的最大价值为f[i-1][j-w[i]]
C[i][j-w[i]]=c[i-1][j]+v[i] //容易简单理解为这句，但不能这么写，C[i][j]的上一状态并不一定是C[i-1][j]
四.算法复杂性分析注意空间复杂度不包括输入输出(函数参数，函数返回值等）
时间复杂度：
由双层for循环可知为O(wn)，注意w与n为不同量纲
空间复杂度：
若不返回C为O（wn),否则为O(1)
运行结果