- 动态规划算法的核心思想:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。
- 下一个子阶段的求解是建立在上一个子阶段的解的基础上的。
- 计数(有多少种方法)、求最大(小)值、求存在性(存不存在一种策略)这些一般都用动态规划算法解决。
- 通过填表的方式进行解决
问题:有一个背包,容量为4磅,现有如表物品
物品 | 重量 | 价格 |
吉他(G) | 1 | 1500 |
音响(S) | 4 | 3000 |
电脑(L) | 3 | 2000 |
- 要求达到的目标为装入的背包的总价值最大,并且重量不超过背包的容量
- 要求装入的物品不能重复
上面这个问题属于01背包(每个物品最多放一个),无限背包指一个物品可以重复使用。
思路分析:
每次 遍历到第i个物品,根据w[i]和val[i]来确定是否将该物品放入背包中(w[i]是指物品的重量,val[i]是指物品的价值)。再让v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。
假如有1、2、3、4磅容量的背包
物品 | 0磅 | 1磅 | 2磅 | 3磅 | 4磅 |
0 | 0 | 0 | 0 | 0 | |
吉他 | 0 | 1500 | 1500 | 1500 | 1500 |
音响 | 0 | 1500(上) | 1500(上) | 1500(上) | 3000 |
电脑 | 0 | 1500(上) | 1500(上) | 2000 | 2000+1500 |
通过上边的填表过程可以得到以下公式
v[i][0]=v[0][j];//表示填入表第一行和第一列都是0 //当准备加入新增的商品的容量大于当前背包的容量时, //就直接使用上一个单元格的装入策略 //当w[i]>j时:v[i][j]=v[i-1][j]; //当准备加入的新增的商品的容量小于等于当前背包的容量, //装入的方式: //v[i-1][j]:就是上一个单元格的装入的最大值(方案) //val[i]:表示当前商品的价值 //v[i-1][j-w[i]]:装入i-1商品到剩余空间j-w[i]的最大值。 当j>=w[i]时:v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+val[i]}
完整代码
package 十大算法; public class 动态规划背包问题 { public static void main(String[] args) { int[]w= {1,4,3};//物品的重量 int[]val= {1500,3000,2000};//物品的价值 int m=4;//背包的容量 int n=val.length;//物品的个数 //创建二维数组表 //v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。 int[][]v=new int[n+1][m+1]; int[][]path=new int [n+1][m+1];//路径 for(int i=0;i<v.length;i++) { v[i][0]=0; } for(int i=0;i<v[0].length;i++) { v[0][i]=0; } //动态规划处理 for(int i=1;i<v.length;i++) {//不处理第一行 for(int j=1;j<v[0].length;j++) {//不处理第一列 //公式 if(w[i-1]>j) {//因为程序的i是从1开始的,因此原来公式中的w[i]修改成w[i-1],下同。 v[i][j]=v[i-1][j]; }else { //v[i][j]=Math.max(v[i-1][j],v[i-1][j-w[i-1]]+val[i-1]); if(v[i-1][j]<v[i-1][j-w[i-1]]+val[i-1]) { v[i][j]=v[i-1][j-w[i-1]]+val[i-1]; path[i][j]=1; }else { v[i][j]=v[i-1][j]; } } } } for(int i=0;i<v.length;i++) { for(int j=0;j<v[i].length;j++) System.out.print(v[i][j]+" "); System.out.println(); } int i=path.length-1;//行的最大下标 int j=path[0].length-1;//列的最大下标 while(i>0 && j>0) { if(path[i][j]==1) { System.out.printf("第%d个商品放入到背包\n",i); j-=w[i-1];//w[i-1] } i--; } } }
评论 抢沙发