动态规划解决背包问题

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

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

物品重量价格
吉他(G)11500
音响(S)43000
电脑(L)32000
  • 要求达到的目标为装入的背包的总价值最大,并且重量不超过背包的容量
  • 要求装入的物品不能重复

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

思路分析:

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


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

物品0磅1磅2磅3磅4磅
00000
吉他01500150015001500
音响01500(上)1500(上)1500(上)3000
电脑01500(上)1500(上)20002000+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--;
 }
}
}

 

分享到:
赞(1) 打赏

评论 抢沙发

评论前必须登录!

 



觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00

      登陆仅提取账号昵称,并无其他功能。

      为了服务器更好的运行,请使用第三方账号登陆。

      授权名称使用的公安备案名称——菜鸟奋斗历程,请知悉。