动态规划解决背包问题

• 动态规划算法的核心思想：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。
• 下一个子阶段的求解是建立在上一个子阶段的解的基础上的。
• 计数（有多少种方法）、求最大（小）值、求存在性（存不存在一种策略）这些一般都用动态规划算法解决。
• 通过填表的方式进行解决

问题：有一个背包，容量为4磅，现有如表物品

• 要求达到的目标为装入的背包的总价值最大，并且重量不超过背包的容量
• 要求装入的物品不能重复

上面这个问题属于01背包（每个物品最多放一个），无限背包指一个物品可以重复使用。

思路分析：

每次 遍历到第i个物品，根据w[i]和val[i]来确定是否将该物品放入背包中（w[i]是指物品的重量，val[i]是指物品的价值）。再让v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。

假如有1、2、3、4磅容量的背包

通过上边的填表过程可以得到以下公式

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--;
 }
}
}