服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java背包问题求解实例代码

Java背包问题求解实例代码

2021-01-21 12:06jayxu无捷之径 Java教程

这篇文章主要介绍了Java背包问题求解实例代码,其中涉及两种背包:01和完全背包。分别讲述了两种背包的思路和实现方法,具有一定参考价值,需要的朋友可以了解下。

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品,如何选择物品放入背包使物品的价值最大。其中又分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、二维数组法

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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--;
    }
  }
}

输出:

?
1
2
3
4
5
6
7
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]]的值。

伪代码如下:

?
1
2
3
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、一维数组法(无须装满)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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]);
  }
}

输出

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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]);
  }
}

输出

?
1
2
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)的算法

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

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]);
   }
  }

输出

?
1
 

总结

以上就是本文关于Java背包问题求解实例代码的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出,小编会及时回复大家并进行修改,努力给广大编程工作及爱好者提供更优质的文章和更好的阅读体验。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/ls5718/article/details/52227908

延伸 · 阅读

精彩推荐