Example code for solving knapsack problem in Java

This article mainly introduces the Java knapsack problem solving example code, which involves two kinds of knapsacks: 01 and complete knapsack. The ideas and implementation methods of the two backpacks are described respectively, which has certain reference value and friends in need can learn about it.

The backpack problem mainly refers to a backpack with a given capacity and a number of items with a certain value and weight. How to choose the items to put into the backpack to maximize the value of the items. It is divided into 01 backpack and unlimited backpack. Here we mainly discuss the 01 backpack, which means that each item can be placed at most one. The infinite backpack can be converted into an 01 backpack.

Let’s first talk about the main idea of ​​the algorithm and use dynamic programming to solve it. Each time the i-th item is traversed, it is determined whether the item needs to be put into the backpack based on w[i] and v[i]. That is, for the given n items, let v[i] and w[i] be the value and weight of the i-th item respectively, and C is the capacity of the backpack. Let v[i][j] represent the maximum value of the first i items that can be loaded into a backpack with capacity j. Then we have the following results:

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

Okay, our algorithm is based on these three conclusion formulas.

1. 01 backpack:

1. Two-dimensional array method

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

Output:

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个物品装入

The time and space complexity of the above method are both O(N*V), where the time The complexity can basically no longer be optimized, but the space complexity can be optimized to O(V).

First consider how to implement the basic idea mentioned above. There must be a main loop i=1..N, and each time the two-dimensional array f[i][0..V] is calculated all values. So, if only one array f[0..V] is used, can it be guaranteed that after the i-th loop ends, f[v] represents the state f[i][v] we defined? f[i][v] is derived recursively from the two sub-problems f[i-1][v] and f[i-1][v-c[i]]. Can we ensure that f[i][v ] (that is, when f[v] is pushed in the i-th main loop), can the values ​​​​of f[i-1][v] and f[i-1][v-c[i]] be obtained? In fact, this requires us to push f[v] in the order v=V..0 in each main loop, so as to ensure that when f[v] is pushed, f[v-c[i]] saves the state f[i -1][v-c[i]] value.

The pseudo code is as follows:

##

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

The sentence f[v]=max{f[v],f[v-c[i]]} is correct It is equivalent to our transfer equation f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}, because now f[v-c[i] ] is equivalent to the original f[i-1][v-c[i]]. If the cyclic order of v is changed from the reverse order above to the order, then it becomes f[i][v], which can be deduced from f[i][v-c[i]], which is inconsistent with the meaning of this question, but it is another An important knapsack problem P02 is the simplest solution, so it is very necessary to learn to solve the 01 knapsack problem using only one-dimensional arrays.

Among the questions we have seen about finding the optimal solution to the knapsack problem, there are actually two different ways to ask the question. Some questions require the optimal solution when the backpack is "just filled", while other questions do not require that the backpack must be filled. One way to distinguish between these two questions is to make a difference during initialization.

If it is the first question, which requires the backpack to be filled exactly, then during initialization except f[0] which is 0, other f[1..V] are set to -∞, so that It can be guaranteed that the final f[N] is an optimal solution that just fills the backpack.

If there is no requirement to fill the backpack, but you only want the price to be as large as possible, all f[0..V] should be set to 0 during initialization.

why? It can be understood this way: the initialized f array is actually the legal state when no items can be put into the backpack. If the backpack is required to be exactly full, then only the backpack with a capacity of 0 may be "exactly filled" with nothing with a value of 0. There is no legal solution for backpacks with other capacities and they are in an undefined state, and their values ​​are all It should be -∞. If the backpack does not have to be filled, then a backpack with any capacity has a legal solution of "packing nothing". The value of this solution is 0, so the initial state values ​​are all 0.

2. One-dimensional array method (no need to fill)

##

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

Output

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

3. One-dimensional array method (must be filled)

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

Output

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

2. Complete backpack
There are N kinds of items and a backpack with a capacity of V. Each item has Unlimited pieces available. The cost of the i-th item is c[i] and the value is w[i]. Find which items can be packed into a knapsack so that the total cost of these items does not exceed the knapsack capacity and the sum of their values ​​is maximum.

But we have a better O(VN) algorithm.

Algorithm of O(VN)
This algorithm uses a one-dimensional array, let’s look at the pseudo code first:

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

You will find that this pseudocode is only different from the pseudocode of P01 in the loop order of 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]); 
   } 
  }

Output

25

总结

The above is the detailed content of Example code for solving knapsack problem in Java. For more information, please follow other related articles on the PHP Chinese website!