PS：本文为转载文章，阅读原文会更具可读性，文末有原文链接一、概述动态规划算法二、背包问题三、动态规划求解背包问题的算法3.1货物的不可重复装载3.2思路分析一、动态规划算法概述（一）动态规划算法的思路是：分大问题分解成小问题去求解，这样就可以得到最优解，一步步求解处理算法。(2)动态规范算法与分治算法非常相似。思路是将待解决的问题分解成n个子问题，先求解子问题，再从子问题中得到原问题的解。(3)动态规划问题与分治算法的区别在于分解后的子问题不是相互独立的。以获得最终的解决方案。(4)动态规划可以通过填表的方式一步步推进，最终得到最优解。2.背包问题这里是一个背包问题。有一个容量为4磅的背包，需要装下表1中的物品，请问背包里的物品如何才能最值钱且重量不超过4磅？图3.动态规划算法解决了上面的背包问题。放入的物品总质量不能超过4磅，装入背包的物品的价值必须最大化。这里，假设放入的货物不能重复。可以用一个二维表来表示。3.1不能重复加载的产品我先画一个表格2，然后我对这个表格2做一个详细的说明，如下图；图片说明：纵列表示背包能装多少重量，横表示物品种类和物品数量，行列交叉处出现的数据代表背包中物品总和的最大值背包可以容纳。好了，我们现在来分析一下表2中的数据。第一行数据全为0，这样好理解吗？不管背包能装多大的重量，只要没有放任何物品，就是0；第一列数据全部为0，因为背包可以装0磅；我们看第二行第二列到第二行的数据第五列的数据，首先第二行能放的物品只能是鞋子，不能重复对不对？那么背包（重量大于或等于1磅）无论能装多少磅的物品，它只能装1磅的鞋子，对吧？那自然是1500。我们来看第三行第二列到第三行第五列的数据。第三排可以放的物品是鞋子和音响，同一个物品最多只能放一件。第三排第二到第三列第四列只能装1磅的鞋子，放不下音箱（音箱重4磅），所以是1500，第三排第五列可以只需拿着一个4磅重的扬声器。一双鞋更值钱，对吧？第四排可以放的物品有鞋子、音响和电脑。好了，现在看第四行第二列到第四行第三列。因为第二列和第三列只能容纳1磅和2磅，对吧？然后只能放一双鞋，所以是1500；第四排第四列可以放3磅，就是可以放一双鞋或者一台电脑，因为电脑比鞋子值钱，所以放电脑比较贵。比较好，所以是2000；看第四行第五列，背包可以装4磅，所以这里有两个更好的选择，一个是放一双鞋和一台电脑，一个是只放一个音响，和看看放一双鞋和一台电脑的解是否更有价值，所以1500+2000就是3500。从表2中，我们可以总结出（1）行表示背包容量从0到指定容量。这是第一步。将大容量背包转化为小容量背包，计算子问题的最优解，然后逐步增加容量，计算出最终问题的最优解。(2)竖行代表商品信息，第一横行为空，作为初始数据的对比值；竖排是第二步，先把一个商品放入背包，计算最优解，逐渐增加商品的种类和商品数量，计算出最终的最优解。(3)决赛桌右下角的格子是数据的最优解；看表2右下角的数据3500是不是最优解。3.2思路分析(1)采用动态规划求解问题。假设给定n件物品，设v[i]和w[i]分别为第i件物品的价值和重量，C为背包的容量。(2)对于每次遍历的第i个物品，根据w[i]和v[i]判断该物品是否需要放入背包；这句话是什么意思？我举个例子，你就明白了。看表2第四行第四列2000的数据，首先第四列背包的最大容量是3磅吧？第四排可以放的东西是鞋子、音响和电脑吧？但是音响比背包容量大，只能放鞋子和电脑。鞋子和手机的重量超过3磅，所以我只能选择鞋子和电脑中的一个放进去，因为电脑比鞋子更值钱。正确的？所以放电脑比较值钱吧？所以是根据w[i]和v[i]来判断物品是否需要放入背包。(3)令vi表示容量为j的背包中前i件物品中所能装入的最大值；这句话是什么意思？再举个例子，看表2第三行第五列的3000，此时i为2，j为4，vi为v2，即v2为3000；第二排唯一的商品是一双鞋子错了吗？第三排可以装的商品包括第二排可以装的商品，也就是说第三排可以装的商品是鞋子和音响；如果鞋子和音响同时放进背包里（背包容量是4磅，j=4）肯定放不下吧？所以从鞋子和音响中选出最值钱的放入背包，所以vi表示前i件物品中容量为j的背包能装的最大价值。现在我们可以从思路分析和表2中总结出以下公式；(1)vi=v0=0，其中i代表行，j代表列；看表2，第一列的数据是0吗？第一行的数据也是0吗？(2)当w[i]>j时，有vi=vi-1，w表示第i+1行产品的重量；例如：看表2第三行第二列，i=2，w[i]=4，j=1，v2=v2-1=1500。(3)当j>=w[i]，有vi=max{vi-1,vi-1]+v[i]}，v[i]表示第i+1行商品的价格；例如：见表2，看第四行第五列的数据，j=4，i=3，w[3]=3，v[3]=2000，则v3=max{v3-1,v3-1]+v[3]}=max{3000,3500},所以v3=3500.好了，现在就用代码来实现吧；(1)新建Test类：packagecom.xiaoer.demo;/**动态编程：背包问题**/publicclassTest{publicstaticvoidmain(String[]args){Testtest=newTest();//产品名称数组String[]nameArr={"shoes","audio","computer"};//产品权重数组int[]weightArr={1/*shoes*/,4/*audio*/,3/*computer*/};//产品价格数组int[]priceArr={1500/*shoes*/,3000/*audio*/,2000/*computer*/};//背包容量intpackageCapacity=4;//将不可重复的物品放入背包test.backpackWithoutRepeat(nameArr,weightArr,priceArr,packageCapacity);}/***装入背包*@paramnameArr商品名数组*@paramw物品重量数组*@parampriceArr商品价格数组*@parampackageCapacity背包容量*/privatevoidbackpackWithoutRepeat(String[]nameArr,int[]w,int[]priceArr,intpackageCapacity){/***声明一个可以加载的包裹二维价格表0、1、2、3磅……背包；例如：就像v数组就是表2中的数据*/int[][]v=newint[nameArr.length+1][packageCapacity+1];//构建一个可能装入背包的二维数组//值为0表示不会装入背包，值为1表示可能装入背包int[][]contentArr=新整数[nameArr.length+1][packageCapacity+1];/***为什么i开头是1而不是0？看表2的数据，第一行是全0吗？*/for(inti=1;i
