1. Introduction

The general introduction of the backpack problem is as follows: There is a backpack with a total capacity of V. Given some items, their volume is stored in array V, and their value is stored in array W. Select some items from these items and put them into the backpack to maximize the total value of the backpack.

2. 0/1 backpack problem

2.1 Solution

The key to the 0/1 backpack problem is that there is only one item per item, so for an item, it either goes in the backpack or it doesn’t go in the backpack. We can create a two-dimensional array f to record the result and list the following formula according to the problem:

F [I] [j] = Max {f [j], [I - 1] f [I - 1] [j - v [I]] + w} [I] note: f [I] [j] said when choosing range for the first item, I and with total capacity backpack j, the great value of the backpack. It's important to understand that.Copy the code

When the total backpack capacity is J, for item I:

  • If the item I is not put in the backpack, then the value is f[i-1][J]
  • If the item I is in the backpack, then the value is F [i-1][J-V [I]]+ W [I]
  • Then take the maximum of these two values and store them in f[I][j]

2.2 Code Implementation

/** * 0/1 backpack problem *@paramV Volume of each item *@paramW Value of each item *@paramVolume Total capacity of the backpack *@return* /
public int zeroOneKnapsack(int[] v, int[] w, int volume) {
    if(v.length ! = w.length) {throw new IllegalArgumentException("The length of the volume array is inconsistent with the length of the value array!");
    } else {
        For convenience, insert an invalid value at the first position of array v and array w
        int[] newV = new int[v.length + 1];
        int[] newW = new int[w.length + 1];
        for (int i = 0; i < newV.length; i++) {
            if(i ! =0) {
                newV[i] = v[i - 1];
                newW[i] = w[i - 1];
            } else {
                newV[i] = -1;
                newW[i] = -1;
            }
        }
        v = newV;
        w = newW;

        // Start counting
        int[][] f = new int[v.length][volume + 1];
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j <= volume; j++) {
                if (j >= v[i]) {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
                } else {
                    f[i][j] = f[i - 1][j]; }}}return f[v.length - 1][volume]; }}Copy the code

2.3 Optimization of result set space

A careful observation of the formula f[I][j] = Max{f[i-1][j], f[i-1][j-v[I]]+w[I]} and the code shows that, for outer cycle I, it is actually compared with the result of the previous cycle (i-1) each time, regardless of the earlier cycle. So we can optimize the result set to be one-dimensional. The code is as follows:

/** * 0/1 knapsack problem to optimize the array space for recording results *@paramV Volume of each item *@paramW Value of each item *@paramVolume Total capacity of the backpack *@return* /
public int zeroOneKnapsack2(int[] v, int[] w, int volume) {
    if(v.length ! = w.length) {throw new IllegalArgumentException("The length of the volume array is inconsistent with the length of the value array!");
    } else {
        int[] f = new int[volume + 1];

        for (int i = 0; i < v.length; i++) {
            F [j] and f[j - v[I]] on the right-hand side of the equation are the results of the previous calculation
            // If j is in the positive order, then for the outer loop, it is actually compared with the round, which is not in accordance with the logic "with i-1".
            for (int j = volume; j >= v[i]; j--) {
                if (i == 0) {
                    f[j] = w[i];
                } else{ f[j] = Math.max(f[j], f[j - v[i]] + w[i]); }}}returnf[volume]; }}Copy the code

3. Complete knapsack problem

The complete knapsack problem is similar to the 0/1 knapsack problem, except that in this problem, the optional number of each item is K, k∈[0, +∞). Under normal circumstances, it can be solved by traversing K again, but at this time the complexity reaches O(n^3). It is time-consuming and can be optimized to O(n^2), with the following pseudo-code:

for (int i = 0; i < v.length; i++)
	for (int j = v[i]; j <= V; j++)
		f[j] = Max{f[j], f[j-v[i]]+w[i]};
Copy the code

The magic point is that when the positive order traversal of J is carried out, the traversal discussion of K has actually been carried out. If you can’t understand it, it is strongly suggested to follow up the whole calculation process in the form of handwriting, which is my own understanding. The final code is as follows:

/** * Full backpacking problem *@paramV Volume of each item *@paramW Value of each item *@paramVolume Total capacity of the backpack *@return* /
public int completeKnapsack(int[] v, int[] w, int volume) {
    if(v.length ! = w.length) {throw new IllegalArgumentException("The length of the volume array is inconsistent with the length of the value array!");
    } else {
        int[] f = new int[volume + 1];

        for (int i = 0; i < v.length; i++) {
            for (int j = v[i]; j <= volume; j++) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
                System.out.print(f[j] + "\t");
            }
            System.out.println();
        }
        returnf[volume]; }}Copy the code

4. Related links

  • The resources