This is the 31st day of my participation in the August Text Challenge.More challenges in August

0-1 backpack problem

There is a backpack, its Capacity is C. There are now n different items numbered 0… N-1, where each item has a weight of W (I) and a value of V (I). Ask what items can be put into the backpack to maximize the total value of items within the backpack’s capacity.

Violent solution

Each item can be put into the backpack, or not put into the backpack, all the way to find the largest. Time complexity: O((2^n)*n)

F(n,C) consider putting n items into a backpack of capacity C to maximize their value. Accordingly, when we place and consider whether to place the ith item there are two strategies in the backpack, namely, put, don't put; F(i,C) = F(i-1,C) // Do not place the i-1 item, consider the previous i-1 item.Or V of I plus F of I minus1,C - W(i)) // Consider placing the ith item in the backpack, where V(I) represents the value of the ith item and W(I) represents the weight of the ith item;
                                // Since it is already in the backpack, the backpack needs to subtract the weight of the ith item, namely, c-w (I).

// Whether the corresponding ith item should be placed in the backpack, that is, take the one that maximizes the placing rule of the two schemes above.
F(i,C) = max( F(i-1,C), V(i)+F(i-1,C - W(i)) )
Copy the code

Recursive solution

    /** * 0-1 knapsacks recursively solve **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@returnThe maximum value that a backpack can carry */
    public int knapsack01(int[] w, int[] v, int c) {
        return bestValue(w, v, c, v.length-1);
    }

    /** * Recursively solve the 0-1 knapsack problem **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@paramIndex Determines whether to place the index item * in the backpack@returnThe current optimal value is */
    private int bestValue(int[] w, int[] v, int c, int index) {
        if (index <= 0 || c <= 0) {
            return 0;
        }
        // Do not consider the index item
        int res0 = bestValue(w, v, c, index - 1);
        int res1;
        if (w[index] <= c) {
            // Consider the index item
            res1 = v[index] + bestValue(w, v, c - w[index], index - 1);
        }
        return Integer.max(res0, res1);
    }
Copy the code

Mnemonic search

    /** ** a * 0-1 knapsack with memorized search recursively solves **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@returnThe maximum value that a backpack can carry */
    public int knapsack01(int[] w, int[] v, int c) {
        int[][] memo = new int[w.length][c+1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return bestValue1(w, v, c, v.length-1, memo);
    }

    /** * Recursively solve 0-1 knapsack problem with mnemonic search **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@paramIndex Determines whether to place the index item * in the backpack@paramThe Memo store calculates whether the optimal solution to put the ith item into the backpack is considered *@returnThe current optimal value is */
    private int bestValue1(int[] w, int[] v, int c, int index, int[][] memo) {
        if (index <= 0 || c <= 0) {
            return 0;
        }
        if(memo[index][c] ! = -1) {
            return memo[index][c];
        }
        // Do not consider the index item
        int res0 = bestValue1(w, v, c, index - 1, memo);
        // Consider the index item
        int res1;
        if (w[index] <= c) {
            // Consider the index item
            res1 = v[index] + bestValue1(w, v, c - w[index], index - 1, memo);
        }

        memo[index][c] = Integer.max(res0, res1);

        return memo[index][c];
    }
Copy the code

Dynamic programming

Assume the backpack has a capacity of 5 and the item information is shown in the table below

ID weight value
0 1 6
1 2 10
2 3 12

Then, the records of mnemonized search can be derived as follows:

ID\W 0 1 2 3 4 5
0 0 6 6 6 6 6
1 0 6 10 16 16 16
2 0 6 10 16 18 22 
    /** * dynamic programming * 0-1 knapsack recursive solution **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@returnThe maximum value that a backpack can carry */
    public int knapsack01(int[] w, int[] v, int c) {
        // The number of items n
        int n = w.length;
        // Declare a two-dimensional array to record the maximum number of items stored in [I item][backpack of capacity w]
        int[][] memo = new int[n][c+1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }

        // Place item 0 in capacity 0,1,2... C backpack, backpack can store the maximum number of items
        for (int j = 0; j <= c; j++) {
            memo[0][j] = w[j] >= v[0]? v[0] : 0;
        }

        // Items of size 1~ N will be placed in the backpack with capacity 0~C, the maximum value of items stored in the backpack

        // I stands for item I
        for (int i = 1; i < n; i++) {
            // j stands for backpack capacity
            for (int j = 0; j <= c; j++) {
                // Try to put item no. I into the backpack, the maximum capacity of the backpack
                int res0 = w[i] <= j ? v[i] + memo[i - 1][j - w[i]] : memo[i - 1][j];
                // Ignore the last good item, the maximum capacity of the backpack
                int res1 = memo[i - 1][j];
                // Compare the two placement methods, take the maximum valuememo[i][j] = Integer.max(res0, res1); }}return memo[n - 1][c];
    }
Copy the code

To optimize the

State transition equation for 0-1 knapsack

F(i,c) = max( F((i-1) , c) , v(i) + F( i-1 , c - w(i) ) )
Copy the code

The element in row I only depends on the element in row i-1, so in theory you only need to keep two rows, not n.

   /** * dynamic programming * 0-1 knapsack recursive solution **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@returnThe maximum value that a backpack can carry */
   public int knapsack01Plus(int[] w, int[] v, int c) {
       // The number of items n
       int n = w.length;
       // Declare a two-dimensional array to record the maximum number of items stored in [I item][backpack of capacity w]
       int[][] memo = new int[2][c + 1];
       for (int[] ints : memo) {
           Arrays.fill(ints, -1);
       }

       // Place item 0 in capacity 0,1,2... C backpack, backpack can store the maximum number of items
       for (int j = 0; j <= c; j++) {
           memo[0][j] = w[j] >= v[0]? v[0] : 0;
       }

       // Items of size 1~ N will be placed in the backpack with capacity 0~C, the maximum value of items stored in the backpack

       // I stands for item I
       for (int i = 1; i < n; i++) {
           // j stands for backpack capacity
           for (int j = 0; j <= c; j++) {
               // Try to put item no. I into the backpack, the maximum capacity of the backpack
               int res0 = w[i] <= j ? v[i] + memo[(i - 1) % 2][j - w[i]] : memo[(i - 1) % 2][j];
               // Ignore the last good item, the maximum capacity of the backpack
               int res1 = memo[(i - 1) % 2][j];
               // Compare the two placement methods, take the maximum value
               memo[i % 2][j] = Integer.max(res0, res1); }}return memo[(n - 1) % 2][c];
   }
Copy the code

To optimize the

Memo [i-1][<j] = memo[i-1][<j] = memo[i-1] = memo[i-1] = memo[I] From memo[I][0]–> Memo [I][c] to memo[I][c]–> Memo [I][0], we can use a one-dimensional array to solve the knapsack algorithm by repeatedly reusing the cells of the array in a row.

    /** * dynamic programming * 0-1 knapsack recursive solution **@paramW Item weight *@paramV Item value *@paramC Backpack capacity *@returnThe maximum value that a backpack can carry */
    public int knapsack01Plus(int[] w, int[] v, int c) {
        // The number of items n
        int n = w.length;
        // Declare a two-dimensional array to record the maximum number of items stored in [I item][backpack of capacity w]
        int[] memo = new int[c + 1];
        Arrays.fill(memo, -1);
        // Place item 0 in capacity 0,1,2... C backpack, backpack can store the maximum number of items
        for (int j = 0; j <= c; j++) {
            memo[j] = w[j] >= v[0]? v[0] : 0;
        }
        // Items of size 1~ N will be placed in the backpack with capacity 0~C, the maximum value of items stored in the backpack
        // I stands for item I
        for (int i = 1; i < n; i++) {
            // j stands for backpack capacity
            for (int j = c; j >= w[i]; j--) {
                // Try to put item no. I into the backpack, the maximum capacity of the backpackmemo[j] = Integer.max(v[i] + memo[j - w[i]], memo[j]); }}return memo[c];
    }
Copy the code

0-1 backpack variant

  1. Assume that each item can be used indefinitely

Train of thought

Although each item can be used indefinitely, the backpack capacity is limited, so, each item has a maximum use, so we can convert the infinite into a finite backpack problem. 2. Multi-dimensional cost backpacks And items have a corresponding volume and capacity. Both constraints need to be met to maximize the value of what the backpack can carry.

Train of thought

3. Item exclusive constraint, item dependent constraint

Partition Equal Subset Sum

Given a non-empty array whose elements are all positive integers, can the array be divided into two parts such that the sum of the two parts is equal?

Eg:

  • [1, 5, 11, 5], which can be divided into two parts: [1, 5, 5] and [11], returns true
  • [1, 2, 3, 5], cannot split an element into two parts to make it equal, returns false

The size of the backpack is the sum of all the elements in the array. The corresponding state transition equation is:

F(n,c) consider filling a backpack of capacity C with n items.

F(i) = F(i-1,C)||F(i-1,C-W(i))
Copy the code

Explain that F(I) stands for whether the backpack can be filled up considering the ith item. W(I) represents the weight of the i-th item. If the i-th item is put into the backpack, it is F(i-1, C-w (I)). If the i-th item is not put into the backpack, the weight of the backpack is the weight of the i-1 item before consideration, namely, F(I -1,C), and they eventually find a way to fill the backpack.

Brute force

    private boolean partitionEqualSubSetSum(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2= =1) {
            return false;
        }
        return partitionEqualSubSetSumCore(arr, sum / 2, arr.length - 1);
    }

    private boolean partitionEqualSubSetSumCore(int[] arr, int c, int index) {
        if (c == 0) {
            return true;
        }
        if (index < 0 || c < 0) {
            return false;
        }
        return partitionEqualSubSetSumCore(arr, c, index - 1) ||
                partitionEqualSubSetSumCore(arr, c - arr[index], index - 1);
    }
Copy the code

Mnemonic search

    private boolean partitionEqualSubSetSumWithMemo(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2= =1) {
            return false;
        }
        // Memo [I][c] indicates if I items can fill a backpack of size C
        // 0 means it cannot be filled, 1 means it can be filled, and -1 means it is not filled
        int[][] memo = new int[arr.length][sum / 2+1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return partitionEqualSubSetSumWithMemoCore(arr, sum / 2, arr.length - 1, memo);
    }

    private boolean partitionEqualSubSetSumWithMemoCore(int[] arr, int c, int index, int[][] memo) {
        if (c == 0) {
            return true;
        }
        if (index < 0 || c < 0) {
            return false;
        }
        if(memo[index][c] ! = -1) {
            return memo[index][c]==1;
        }
        boolean res = partitionEqualSubSetSumWithMemoCore(arr, c, index - 1, memo) ||
                partitionEqualSubSetSumWithMemoCore(arr, c - arr[index], index - 1, memo);
        memo[index][c] = res ? 1 : 0;
        return res;
    }
Copy the code

Dynamic programming

   private boolean partitionEqualSubSetSum(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2= =1) {
            return false;
        }
        int c = sum / 2;
        boolean[] memo = new boolean[c + 1];
        // First try to put the 0th item into the backpack
        for (int i = 0; i <= c; i++) {
            memo[i] = i == arr[0];
        }
        // Put items 1-n into the backpack
        for (int i = 1; i < arr.length; i++) {
            for (int j = c; j >= arr[i]; j--) {
                memo[j] = memo[i - 1] || memo[c - arr[i]]; }}return memo[c];
    }
Copy the code

Coin Change

Given coins of different denomination, ask how many coins are needed to make up the specified amount. The algorithm returns this number. If not, return -1. If given coin amount is [1,2,5],amount = 11, return 3, (1,5,5) If given coin amount is [2],amount = 3, return -1

Combination Sum

Given an array of integers in which there are no duplicated elements, how many possibilities are there for the number in the array to make up an integer target,

Eg:

Such as: num [1, 2, 3] the combination of the target = 4 May return,1,1,1 [1],,1,2 [1], [1, 2, 1], [1, 3],,1,1 [2], [2], [3, 1] algorithm returns 7, note: order

Ones and Zeros

Given an array of strings in which each string is a 0, 1 string, how many 01 strings can be formed with m 0’s and n 1’s?

[constraint]

  1. M and n do not exceed 100
  2. The number of elements in the array does not exceed 600
  • For example: [10, 0001, 111001, 1, 0]

Given five zeros and three ones, a maximum of four elements can be formed, 10,0001,1,0

  • For example, [10, 0, 1], given a 0 and a 1, can form two elements at most, namely, 0 and 1

Word Break

Given a non-empty string S and an array of non-empty strings wordDict, ask if you can concatenate different strings from wordDict to form a non-empty string S, assuming there are no duplicate strings in wordDict

  • For example, s = “leetcode” wordDict = [“leet”, “code”] is returnedtrue

Target Sum

Given a non-empty sequence of numbers, how many possibilities are there if the number is preceded by a “+” or a “-” so that the result is the given integer s? Such as: nums = (1, 1, 1, 1, 1] s = 3 answer is 5-1 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1-1

Longest ascending subsequence

Given a sequence of integers, find the longest ascending subsequence length. (It is not required that the subsequence be continuous, as long as the relative positions remain the same)

  • [10, 9, 2, 5, 3, 7, 101, 18], the longest ascending subsequence length is 4

The longest ascending subsequence is [2, 5, 7, 101].

solution

LIS(I) represents the length of the longest ascending subsequence ending in the ith digit. LIS(I) represents the longest ascending subsequence length that can be obtained by selecting nums[I] within the range of 0-i.

LIS(i) = max( 1 + LIS(j) if(nums[i]>nums[j]) )
         j < i
Copy the code

The corresponding ascending subsequence of the ith digit is: the maximum length of the ascending subsequence of the previous nums[j] (nums[j]<nums[I]) +1

[10, 9, 2, 5, 3, 7, 101, 18]

num\i 0 1 2 3 4 5 6 7
10 1
9 1
2 1
5 2
3 2
7 3
101 4
8 4

Where I represents the maximum length of the ascending subsequence of the ith element.

  1. The largest ascending sequence with the 0th element 10 is itself, 1
  2. The first element is 9, and there is no previous element smaller than 9, so the maximum ascending length is 1
  3. The second element is 2, and there is no previous element smaller than 2, so the maximum ascending length is 1
  4. The third element is 5, and the previous element 2 is less than 5, so the maximum ascending length of 2 is the maximum ascending length of 2 +1, i.e. 1+1=2
  5. The fourth element is 3, and the previous element 2 is less than 5, so the maximum ascending length of 2 is the maximum ascending length of 2 +1, i.e. 1+1=2
  6. The fifth element is 7, and the preceding elements 2, 5, and 3 are all smaller than 7. Choose the maximum ascending length +1, that is, 2+1=3
  7. The sixth element, 101, takes the value of the previous largest ascending element smaller than it +1, that is, 3+1=4
  8. The seventh element is 8, and the value of the previously smaller ascending element is +1, that is, 3+1=4

Finally, the maximum ascending length is 4

coded

    int lis(int[] arr) {
        if (arr == null) {
            return -1;
        }
        if (arr.length <= 1) {
            return arr.length;
        }
        int len = arr.length;
        int[] memo = new int[len];
        Arrays.fill(memo, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    memo[i] = Integer.max(memo[i], memo[j] + 1); }}}return max(memo);
    }

    private int max(int[] array) {
        if (array == null) {
            throw new IllegalArgumentException("The Array must not be null");
        } else if (array.length == 0) {
            throw new IllegalArgumentException("Array cannot be empty.");
        } else {
            int max = array[0];

            for (int j = 1; j < array.length; ++j) {
                if(array[j] > max) { max = array[j]; }}returnmax; }}Copy the code

Time complexity O(n^2)

Wiggle Subsequence

A sequence in which the size of adjacent digits alternates in ascending or descending order is called a wiggle sequence, for example: [1, 7, 4, 9, 2, 5] is a wiggle sequence, but [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not.