动态规划背包问题算法分析,用动态规划求解背包问题
背包问题是一个组合优化的NP完全问题。问题可以描述为：给定一组物品，每个物品都有自己的重量和价格。在有限的总重量内，如何选择才能让物品总价最高？
动态规划算法的思想动态规划算法处理多阶段的复杂决策问题。动态规划算法类似于分治算法。它的基本思想是把要解决的问题分解成若干个子问题(阶段)，然后分别求解每个子问题(阶段)，最后将子问题的解组合起来得到原问题的解。但与分治算法不同的是，子问题往往不是独立的，而是相互关联又互不相同的。
动态规划算法问题求解的目标是获得导致问题最优解的最优决策序列(最优策略)。对于一个决策序列，可以用一个数值函数(目标函数)来衡量这个决策的质量。
最优性原理动态规划算法的最优性原理：一个最优决策序列具有这样一个性质：不管初始状态和第一个决策如何，对于前一个决策形成的状态，其余的决策必须根据前一个决策产生的新状态形成一个最优决策序列。
最优性原理体现在问题的最优子结构特征中。对于一个问题，如果一个大规模相似子问题的最优解可以由一个小规模子问题的最优解得到，则最终可以得到给定问题的最优解，即该问题最优解所包含的子问题的最优解。这个性质叫做最优子结构性质。由较小问题的解构造较大问题的解时，最优子结构的特点是只需要考虑子问题的最优解，然后由子问题的最优解自底向上递归构造整个问题的最优解。保证了通过求解子问题的最优解可以得到原问题的最优解，最优子结构的特征是动态规划算法求解问题的必要条件。
动态规划算法的三个特点如果解决的问题满足最优性原理，就意味着用动态规划算法解决问题是可能的。在分析问题的最优子结构时，所用的方法是通用的。需要注意的是，描述问题最优子结构的方法有很多种，有些表示方法求解速度更快(占用空间少，问题维数低)。定义递归最优解。动态规划的每一个决策都依赖于子问题的解。动态规划算法求解优化问题的步骤是：找出最优解的结构，具体来说就是看问题是否满足最优子结构特征；其次，递归定义一个最优解的值，即在原问题和子问题之间构造一个递归方程。原问题的最优解可以通过子问题的最优解得到。自下而上计算最优解的值(最优解的目标函数值)。子问题的分解是基于原问题的分解，这些子问题的分解过程是相互独立的。在分解原问题的过程中，会出现大量共享的重叠子问题。为了避免大量重叠子问题的重复计算，一般动态规划算法都是自下而上，每个问题只求解一次，保存求解子问题的最优值。当需要求解这个子问题时，可以在一个常数时间内检查结果，而不是递归求解每个问题，从而提高动态规划算法的效率。动态规划算法中的0/1背包问题。0/1背包问题的规则是不允许拆分物品，即只有当物品处于放入和不放入两种基本状态时，才需要用动态规划算法找出如何放置物品，才能使背包中物品的总价值达到最高。
例子
有一个负重10的背包。文章有四种。eac的重量
//m表示背包的容量，A表示有多少种物品，数组W用来存储每种物品的重量，数组val用来存储每种物品的值。
公共类my {
公共静态void main(String[] args){
Scanner scanner=新扫描仪(system . in)；
System.out.print(请输入背包的容量：)；
int m=scanner . nextint()；
Scanner inScanner=新扫描仪(system . in)；
System.out.print(请输入项数：)；
int a=in scanner . nextint()；
int[]w=new int[a 1]；
System.out.print(请输入物品重量： )；
for(int I=1；i i ) {
w[I]=in scanner . nextint()；
}
int[]val=new int[a 1]；
System.out.print(请输入该项的值： )；
for(int I=1；i i ) {
val[I]=in scanner . nextint()；
}
int n=val.length
int[][]path=new int[n 1][m 1]；
//创建一个二维数组
//v[i][j]:表示前I个物品能装进一个容量为j的背包的最大值。
int[][]v=new int[n 1][m 1]；
//初始化第一行和第一列
for(int I=0；一.长度；I) {//v.length:获取二维数组中的行数
v[I][0]=0；//将第一列设置为0
}
for(int I=0；我v[0]。长度；I) {//v[0]。length:获取二维数组的列数
v[0][I]=0；//将第一行设置为0
}
for(int I=1；一.长度；I) {//int i=1不处理第一行
for(int j=1；j v[0]。长度；J) {//int j=1不处理第一列
if (w[i - 1] j) {
v[I][j]=v[I-1][j]；
}否则{
if(v[I-1][j](val[I-1]v[I-1][j-w[I-1]]){
v[I][j]=val[I-1]v[I-1][j-w[I-1]]；
//将当前情况记录到path中
path[I][j]=1；
}否则{
v[I][j]=v[I-1][j]；
}
}
}
}
//输出二维数组：
for (int[] ints : v) {
system . out . println(arrays . tostring(ints))；
}
//输出我们最后放进去的那些商品。
int I=path . length-1；//该行的最大下标
int j=path[0]。长度-1；//列的最大下标
While (i 0 j 0) {//从路径的末端看
if (path[i][j]==1) {
System.out.printf(第%d项放在背包里\n ，I-1)；
j-=w[I-1]；
}
I-；
}
}
}进入一个容量为10的背包，里面有4种物品。项目的权重为2、3、4和7，项目的值分别为1、3、5和9。
结果
动态规划算法的优点解决一个给定的问题，我们需要求解它的不同部分(即子问题)，然后将子问题的解组合起来，得到原问题的解。通常很多子问题都很相似，所以动态规划法尽量每个子问题只解一次，这样就减少了计算量：给定子问题的解一旦被计算出来，就会被记忆存储，下次需要同一个子问题的解时，可以直接在表中查找。当重复子问题的数量随着输入的大小呈指数增长时，这种方法特别有用。
版权归作者所有：原创作品来自博主、程序员，转载授权请联系作者，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。