动态规划算法-01背包问题

《动态规划算法-01背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划法求解0-1背包问题一、动态规划法的设计思想动态规划法是数学--“运筹学”中一个决策分析的实现，广泛运用在计算机算法、企业决策、市场营销等领域动态规划法是将待求解的问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经过分解的子问题往往不是独立的。若用分治法求解这类问题，则相同的子问题会被求解多次，以至于最后解决问题需要消耗指数级别的时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已经解决的子问题的答案，在需要时再找出已经求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。

2、为了达到这个目的，可以使用个表来记录已经解决子问题的答案，不管子问题以后是否被用到，只要它计算过，就将其结果填入表中，这就是动态规划法的基本思路动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行的解，每个解对应个值，我们希望找到最大值或者最小值的那个解，其步骤如下：1、找出最优值的性质，并分析其结构特征2、递归定义最优解的值3、自底向上的方式计算出最优值4、根据计算最优值得到的信息，构造一个最优解步骤1—2是基本步骤，在只需求出最优值的情况下步骤4可以省略。若需要求子问题的最优解，则必须执行步骤4，此时在步骤3中计算最优值时，通常记录等多的信息，以

3、便在步骤4中根据所记录的信息快速构造出一个最优解动态规划算法是非常有效的算法技术，那么什么时候使用它呢？或者说其运用场景是什么？若求解问题具有一下性质，可以考虑使用动态规划法：1、最优子结构：如果一个问题的最优解中包含其子问题的最优解，就是说该问题具有最优子结构。这时候贪婪算法可能也使用求解此类问题2、重叠子问题：重叠子问题是指用来求解问题的递归算法可以反复的解同样的问题，而不是总在产生新的问题，即当一个递归算法不断的调用同一个问题时，就说该问题包含重叠子问题，此时若使用分治法递归求解时，则每次遇到子问题都会视为新问题，会极大降低效率，而动态规划法对每个子问题仅计算一次，把

4、解保存到在一个需要时就可以查看的表中二、动态规划法案例：0-1背包问题有n个物品，第i个物品的价值为Vi，重量为Wi，其中Vi和Wi均为非负数，背包容量为W，W为非负数。现考虑如何选择装入背包的物品，使装入背包的物品总价值最大。假设商品有5件，n=5，容量为17，W=17要装入的物品及其价值如下表所示：物品编号12345价值v45101113重量w34789（一）、求解思路1、使用矩阵规划出最优解把求解过程看作是一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包（1）如果一个问题的最优解包含了物品n，即Xn=1，那么其余的X1,X2,….Xn-1一定构成子问题

5、1,2,……n-1在容量为W-wn时的最优解（2）如果这个最优解不包含物品n，即Xn=0，那么其余X1,X2….,Xn-1一定构成子问题1,2….,n-1在容量为W时的最优解根据上述分析，设c[i,w]表示背包容量为w时i个物品最优解的总价值，得到公式：0i=0或w=0C[i,w]=c[i–1,w]wi>wmax{c[i–1,w–wi]+vi,c[i–1,w]}i>0且wi<=w2、根据物品的件数i=5、包的容量W=17规划“价值”分布矩阵，如下图所示：（1）物品价值重量关系表（2）物品件数—价值分布矩阵（二）程序实现1、Java语言代码实现如下：publicstaticv

6、oidmain(String[]args){int[]goods_weight={3,4,7,8,9};//物品重量int[]goods_value={4,5,10,11,13};//物品价值intm=17;//背包容量intn=5;//物品个数//c[i][j]表示前i个物品能装入容量为Wj的背包中的最大价值intc[][]=newint[n+1][m+1];intpath[][]=newint[n+1][m+1];//初始化第一列和第一行for(inti=0;i

7、{c[0][i]=0;}//通过公式迭代计算for(inti=1;iWj)c[i][Wj]=c[i-1][Wj];else{if(c[i-1][Wj]