In depth analysis of multiple knapsack problem （ The next part ）

Preface

In the previous three articles , We have discussed it carefully 01 knapsack problem and Complete knapsack problem as well as Multiple backpacks Part 1 , In this article, we mainly introduce Multiple knapsack problem An optimization method of —— Binary optimization Multiple backpack , If you haven't seen it yet Multiple backpacks Part 1 , You need to read Multiple backpacks Part 1 .

Introduction to multiple knapsack problem

Yes $N$ Items and a capacity are $V$ The backpack . The first $i$ Items At most $s_i$ Pieces of , The volume of each piece is $v_i$, The value is $w_i$. Find out which items to pack in your backpack , It can make the total volume of the goods not exceed the capacity of the backpack , And the sum of values is the largest .

Be careful ： The meaning of the characters used above is the same in this article .

Multiple knapsack problems are related to 01 knapsack and Completely backpack The difference is in the number of times items are available ,01 knapsack Can only be used once , Multiple backpack It can be used countless times , and Multiple backpack It can be used many times .

Binary optimization of multiple knapsacks

Implementation of binary optimization

In the formal analysis Binary optimization of multiple knapsacks Before , Let's analyze it The time complexity of multiple backpacks , Suppose we have $N$ Item , The average number of each item is $S$, The time complexity of multiple backpacks is $O(NSV)$. The binary optimization of multiple knapsacks can reduce the time complexity to $O(NVlog(S))$.

stay Multiple backpacks Part 1 In the previous article, we mentioned the dynamic transfer equation of multiple knapsacks （ $T=min(S,\frac{V}{v_i})$, among $S$ Indicates the number of times an item can be selected ,$v_i$ Represents the volume of the object ,$V$ Indicates the capacity of the current backpack ）：
$$\begin{gathered} dp[i][j]=max \\ \{ \\ dp[i-1][j], \\ dp[i-1][j-v[i]]+w[i], \\ dp[i-1][j-v[i]\ast 2]+w[i]\ast 2, \\ ..., \\ dp[i-1][j-v[i]\ast T]+w[i]\ast T \\ \} \end{gathered}$$
From the above formula, we can know , For someone who has $S$ Of the items , We should choose a suitable number to maximize our income , This number may be $1,2,3,4,...,S$. We are in the article Multiple backpacks Part 1 It is mentioned that we can put Multiple backpack Turn it into 01 knapsack , We will $S$ Items are logically divided into those with the same volume and value $S$ Two different things , Is divided into $S$ When making dynamic selection, different items are compared with $S$ The same items are the same . For example, for $S$ Same items $A$, We are choosing 3 The profit can reach the maximum at the time of , So for the transformed 01 knapsack problem Just choose 3 One and $A$ Items with the same volume and value can .

According to the above analysis, we can know Multiple backpack Can be transformed into 01 knapsack The reason is that multiple backpacks are transforming into 01 knapsack after ,01 knapsack Can have Multiple backpack choose 1 individual , choose 2 individual , choose 3 individual ,…, choose $S$ The effect of .

And our binary optimization is mainly focused on this place . Multiple backpack Binary optimization of also transforms the multiple knapsack problem into 01 knapsack problem , But not to $S$ The same items are converted into $S$ Different items with the same volume and value . According to the above analysis, we know , We are going to Multiple backpack Turn it into 01 knapsack Then there is the need to ensure 01 knapsack Can achieve Multiple backpack choose 1 individual , choose 2 individual , choose 3 individual ,…, choose $S$ The effect of . So how can we achieve this ？ The following code mainly shows that binary optimization will Multiple backpack Turn it into 01 knapsack What should be added to the collection of the value and volume of the goods .

Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
ArrayList<Integer> v = new ArrayList<>();
ArrayList<Integer> w = new ArrayList<>();
for (int i = 0; i < N; i++) {
    
    //  This means the second  i  The volume of items 
    int vi = scanner.nextInt();
    //  This means the second  i  The value of an item 
    int wi = scanner.nextInt();
    //  This means the second  i  How many items are there 
    int si = scanner.nextInt();
    //  This code is mainly to realize that multiple backpacks can choose 1 individual 
    //  choice 2 individual ,..., choice S The effect of 
    for (int j = 1; j <= si; j *= 2) {
    
        si -= j ;
        v.add(vi * j);
        w.add(wi * j);
    }
    if (si > 0) {
    
        v.add(vi * si);
        w.add(wi * si);
    }
}

Let's take an example to analyze the above code , Suppose we add an item $A$, Its number is 9, The value and volume are 5 and 3. Then gather $v$ And collection $w$ The data are ：
$$v=[3,6,12,6]$$

$$w=[5,10,20,10]$$

The above example will 9 individual $A$ Divided into $A_1$,$A_2$,$A_3$, as well as $A_4$,$A_1$ To $A_4$ Its volume and value are equivalent to 1 individual ,2 individual ,4 individual ,2 One of the $A$ The volume and value of . We mentioned above , We are going to Multiple backpack Turn it into 01 knapsack Then there is the need to ensure 01 knapsack Can achieve Multiple backpack choose 1 individual , choose 2 individual , choose 3 individual ,…, choose $S$ The effect of , So how does the above transformation achieve this effect ？

• One $A$： amount to $A_1$.
• Two $A$： amount to $A_2$.
• Three $A$： amount to $A_1+A_2$, That is, when you choose dynamically $A_1$ and $A_2$ Two items .
• four $A$： amount to $A_3$.
• Five $A$： amount to $A_1+A_3$, That is, when you choose dynamically $A_1$ and $A_3$ Two items .
• six $A$： amount to $A_2+A_3$, That is, when you choose dynamically $A_2$ and $A_3$ Two items .
• Seven $A$： amount to $A_1+A_2+A_3$, That is, when you choose dynamically $A_1$、$A_2$ and $A_3$ Three items .
• Eight $A$： amount to $A_2+A_3+A_4$, That is, when you choose dynamically $A_2$、$A_3$ and $A_4$ Three items .
• Nine $A$： amount to $A_1+A_2+A_3+A_4$, That is, when you choose dynamically $A_1$、$A_2$、$A_3$ and $A_4$ Four items .

I believe that after the above example, you have roughly understood the general implementation process of binary optimization , Binary optimization will also Multiple backpack Turn it into 01 knapsack But different from the previous transformation , We are not going to $S$ Items $A$ Divide into $S$ Items of the same volume and value , Instead, it is divided into volumes and values that are the original items 1 times 、2 times 、3 times ,…,$2^n$ Multiple items , namely $1+2+4+...+2^n+a=S$, among $a$ Is the last remaining remainder （$a<2^{n+1}$）, Like the last one above 2 Namely a = 9 - 1 - 2 - 4. We can know this division , The number of items after we divide will be very small . If the maximum number of items is int Maximum of type , If we divide one by one, we can divide more than 20 100 million items , And the above division , We can't divide more than 32 individual , Therefore, the time complexity is greatly reduced .

Before dividing one by one, our time complexity is $O(NSV)$, The largest time complexity of dividing us as above is $O(NVlog(S))$, among $N$ Represents the number of items ,$S$ Indicates the average number of times an item can be selected ,$V$ Indicates the capacity of the backpack .

The above is how we use binary optimization to Multiple backpack Turn it into 01 knapsack The way , The complete code is as follows （ The following code uses single row array optimization ）：

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    
  public static void main(String[] args) {
    
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int V = scanner.nextInt();
    ArrayList<Integer> v = new ArrayList<>();
    ArrayList<Integer> w = new ArrayList<>();
    for (int i = 0; i < N; i++) {
    
      int vi = scanner.nextInt();
      int wi = scanner.nextInt();
      int si = scanner.nextInt();
      for (int j = 1; j <= si; j *= 2) {
    
        si -= j ;
        v.add(vi * j);
        w.add(wi * j);
      }
      if (si > 0) {
    
        v.add(vi * si);
        w.add(wi * si);
      }
      System.out.println(v);
      System.out.println(w);
    }
    int[] f = new int[V + 1];
    for (int i = 0; i < v.size(); i++) {
    
      for (int j = V; j >= v.get(i); j--) {
    
        f[j] = Math.max(f[j], f[j - v.get(i)] + w.get(i));
      }
    }
    System.out.println(f[V]);
  }
}

The essence of binary optimization

We know that any number has its binary form , Any number can be represented by 2 Add the integer powers of to get ：

If we have 15 Items $A$, Then we will get $A_1$,$A_2$,$A_3$,$A_4$, Their value and volume are $A$ Of 1 times ,2 times ,4 Times and 8 times , These four items can form items equivalent to any integral multiple $A$ The value and weight of , Among this problem is 1, 2, 4, 8 It can make up 1~15 Any number between .

Because we may finally $S$ All items are selected , So when we turn multiple backpacks into 01 Behind the backpack , The value and volume of all transformed items need to be equal to $S$ Items are the same , and $S$ It doesn't necessarily happen to be $n$ Add the values of integer powers , Therefore, it is also mentioned above $a$,$a$ It ensures that we can finally get 1~$S$ Any number between .

summary

This article mainly introduces Multiple knapsack problem Binary optimization of , The logic inside is still a little complicated , You may need to experience it carefully , When you read the text, you can refer to the code and analyze it carefully , It can be understood better .

That's all the content of this article , I hope you can get something , I am a LeHung, See you next time ！！！（ Remember give the thumbs-up Collection ！）

More wonderful content collections can be accessed to the project ：https://github.com/Chang-LeHung/CSCore

Official account ： Worthless research monk , Learn more about computers （Java、Python、 Fundamentals of computer system 、 Algorithm and data structure ） knowledge .