Java背包问题求解实例代码

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分01背包和无限背包,这里主要讨论01背包,即每个物品最多放一个。而无限背包可以转化为01背包。

先说一下算法的主要思想,利用动态规划来解决。每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果:

(1),v[i][0]=v[0][j]=0;
(2),v[i][j]=v[i-1][j] 当w[i]>j
(3),v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 当j>=w[i]

好的,我们的算法就是基于此三个结论式。

一、01背包:

1、二维数组法

public class sf {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] weight = {3,5,2,6,4}; //物品重量
    int[] val = {4,4,3,5,3}; //物品价值
    int m = 12; //背包容量
    int n = val.length; //物品个数
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值
    int[][] path = new int[n+1][m+1];
    //初始化第一列和第一行
    for(int i=0;i<f.length;i++){
      f[i][0] = 0;
    }
    for(int i=0;i<f[0].length;i++){
      f[0][i] = 0;
    }
    //通过公式迭代计算
    for(int i=1;i<f.length;i++){
      for(int j=1;j<f[0].length;j++){
        if(weight[i-1]>j)
          f[i][j] = f[i-1][j];
        else{
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1];
            path[i][j] = 1;
          }else{
            f[i][j] = f[i-1][j];
          }
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]);
        }
      }
    }
    for(int i=0;i<f.length;i++){
      for(int j=0;j<f[0].length;j++){
        System.out.print(f[i][j]+" ");
      }
      System.out.println();
    }
    int i=f.length-1;
    int j=f[0].length-1;
    while(i>0&&j>0){
      if(path[i][j] == 1){
        System.out.print("第"+i+"个物品装入 ");
        j -= weight[i-1];
      }
      i--;
    }
  }
} 

输出:

0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 4 4 4 4 4 4 4 4 4 4
0 0 0 4 4 4 4 4 8 8 8 8 8
0 0 3 4 4 7 7 7 8 8 11 11 11
0 0 3 4 4 7 7 7 8 9 11 12 12
0 0 3 4 4 7 7 7 8 10 11 12 12
第4个物品装入 第3个物品装入 第1个物品装入 

以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。

伪代码如下:

for i=1..N
  for v=V..0
    f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

2、一维数组法(无须装满)

public class sf {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] weight = {3,5,2,6,4}; //物品重量
    int[] val = {4,4,3,5,3}; //物品价值
    int m = 12; //背包容量
    int n = val.length; //物品个数
    int[] f = new int[m+1];
    for(int i=0;i<f.length;i++){   //不必装满则初始化为0
      f[i] = 0;
    }
    for(int i=0;i<n;i++){
      for(int j=f.length-1;j>=weight[i];j--){
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
      }
    }
    for(int i=0;i<f.length;i++){
      System.out.print(f[i]+" ");
    }
    System.out.println();
    System.out.println("最大价值为"+f[f.length-1]);
  }
} 

输出

0 0 3 4 4 7 7 7 8 10 11 12 12
最大价值为12

3、一维数组法(必须装满)

public class sf {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] weight = {3,5,2,6,4}; //物品重量
    int[] val = {4,4,3,5,3}; //物品价值
    int m = 12; //背包容量
    int n = val.length; //物品个数
    int[] f = new int[m+1];
    for(int i=1;i<f.length;i++){   //必装满则f[0]=0,f[1...m]都初始化为无穷小
      f[i] = Integer.MIN_VALUE;
    }
    for(int i=0;i<n;i++){
      for(int j=f.length-1;j>=weight[i];j--){
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
      }
    }
    for(int i=0;i<f.length;i++){
      System.out.print(f[i]+" ");
    }
    System.out.println();
    System.out.println("最大价值为"+f[f.length-1]);
  }
} 

输出

0 -2147483648 3 4 3 7 6 7 8 10 11 12 11
最大价值为11

二、完全背包

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

但我们有更优的O(VN)的算法。

O(VN)的算法

这个算法使用一维数组,先看伪代码:

for i=1..N
  for v=0..V
    f[v]=max{f[v],f[v-cost]+weight}

你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。

public class test{
   public static void main(String[] args){
      int[] weight = {3,4,6,2,5};
      int[] val = {6,8,7,5,9};
      int maxw = 10;
      int[] f = new int[maxw+1];
      for(int i=0;i<f.length;i++){
        f[i] = 0;
      }
      for(int i=0;i<val.length;i++){
        for(int j=weight[i];j<f.length;j++){
          f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);
        }
      }
      System.out.println(f[maxw]);
   }
  } 

输出

25

总结

以上就是本文关于Java背包问题求解实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:Java 蒙特卡洛算法求圆周率近似值实例详解、Java小程序求圆的周长和面积实例、Java编程用栈来求解汉诺塔问题的代码实例(非递归)等,如有不足之处,欢迎留言指出,小编会及时回复大家并进行修改,努力给广大编程工作及爱好者提供更优质的文章和更好的阅读体验。感谢朋友们对本站的支持!

(0)

相关推荐

  • Java使用分治算法实现排序数索引功能示例【二分搜索】

    本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • 浅谈java实现背包算法(0-1背包问题)

    0-1背包的问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题.问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高.问题的名称来源于如何选择最合适的物品放置于给定背包中. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放. 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是: f[i][v]=max{ f[i-1][v], f

  • 详解Java数据结构和算法(有序数组和二分查找)

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • Java背包问题求解实例代码

    背包问题主要是指一个给定容量的背包.若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大.其中又分01背包和无限背包,这里主要讨论01背包,即每个物品最多放一个.而无限背包可以转化为01背包. 先说一下算法的主要思想,利用动态规划来解决.每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中.即对于给定的n个物品,设v[i].w[i]分别为第i个物品的价值和重量,C为背包的容量.再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值.则我们有

  • Java回调函数实例代码详解

    首先说说什么叫回调函数? 在WINDOWS中,程序员想让系统DLL调用自己编写的一个方法,于是利用DLL当中回调函数(CALLBACK)的接口来编写程序,使它调用,这个就 称为回调.在调用接口时,需要严格的按照定义的参数和方法调用,并且需要处理函数的异步,否则会导致程序的崩溃. 这样的解释似乎还是比较难懂,这里举个简 单的例子: 程序员A写了一段程序(程序a),其中预留有回调函数接口,并封装好了该程序.程序员B要让a调用自己的程序b中的一个方法,于是,他通过a中的接口回调自己b中的方法.目的达到

  • java图片添加水印实例代码分享

    本文为大家介绍了java图片添加水印实例代码,java实现水印还是非常方便的,水印可以是图片或者文字,具体内容如下 package michael.io.image; import java.awt.AlphaComposite; import java.awt.Graphics2D; import java.awt.Image; import java.awt.RenderingHints; import java.awt.image.BufferedImage; import java.io

  • 详解json string转换为java bean及实例代码

    详解json string转换为java bean及实例代码 pom中添加如下两个库: <dependency> <groupId>org.codehaus.jackson </groupId> <artifactId>jackson-core-asl</artifactId> <version>1.9.2</version> <scope>provided</scope> </depende

  • Java反射机制实例代码分享

    本文旨在对Java反射机制有一个全面的介绍,希望通过本文,大家会对Java反射的相关内容有一个全面的了解. 阅读本文之前,大家可先行参阅<重新理解Java泛型>. 前言 Java反射机制是一个非常强大的功能,在很多大型项目比如Spring, Mybatis都可以看见反射的身影.通过反射机制我们可以在运行期间获取对象的类型信息,利用这一特性我们可以实现工厂模式和代理模式等设计模式,同时也可以解决Java泛型擦除等令人苦恼的问题.本文我们就从实际应用的角度出发,来应用一下Java的反射机制. 反射

  • Java数组扩容实例代码

    在写程序的过程中,我们常常会碰见数组空间不够用的情况,比如我已经初始化了一个数组int []a = {1,2,3,4,5,6,7,8,9,10} ;这时,我想往数组下标3的位置插入一个元素,该怎么做?用C语言实现太难了吧,需要调用memcpy函数要一个一个偏,但是在java中就不用那么麻烦了,有种叫数组的扩容方式,轻松实现.来看看代码: public class HelloWorld { public static void main(String[] args){ // Scanner s =

  • Kotlin传递可变长参数给Java可变参数实例代码

    本文研究的主要是Kotlin传递可变长参数给Java可变参数的方法,具体实现代码如下. 定义Java可变参数方法 package com.tcl.john.studymvvm.utils; /** * 调用Java方法的工具类 * Created by ZhangJun on 2017/10/25. */ public class CallJavaUtils { public static int addNumbers(String name, int... args) { int result

  • JAVA验证码工具实例代码

    工具类: package com.lhy.web.servlet; import java.awt.BasicStroke; import java.awt.Color; import java.awt.Font; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.FileNotFoundException; import java.io.FileOutputStream; import

  • Java对象流实例代码

    将日期对象和向量对象写入文件,然后从文件中读出并输出到屏幕上 package objstream; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io

  • Java编程Nashorn实例代码

    本文研究的主要是Java编程Nashorn的相关内容,具体如下. Nashorn是什么 Nashorn,发音"nass-horn",是德国二战时一个坦克的命名,同时也是java8新一代的javascript引擎--替代老旧,缓慢的Rhino,符合 ECMAScript-262 5.1 版语言规范.你可能想javascript是运行在web浏览器,提供对html各种dom操作,但是Nashorn不支持浏览器DOM的对象.这个需要注意的一个点. 之前学习Java8的时候恰好写了个简单的例子

随机推荐