Algorithm learning summed up several knapsack problem solving ideas

preface

The author’s algorithm recently learned the stage of dynamic planning, brush a lot of dynamic planning questions, for the knapsack problem in dynamic planning, really headache at the beginning, many questions may just slightly changed some constraints, I can not answer. Although the method of solving this kind of problem is similar, there are many varieties, different varieties, it needs to modify the problem solving ideas are very need to be carefully thought out, so at the beginning, not only the success rate of solving the problem is not high, the speed of solving the problem is very slow. Here, I based on my own practice and the experience of some predecessors, summed up several relatively basic problem solving methods, to improve the success rate and efficiency of solving backpack problems.

Classic 0-1 backpack problem

I will first make a brief introduction and review of the most basic 0-1 knapsack problem, the other knapsack problems are basically variations of this basic problem.

I have a backpack, and it has capacity C. There are now n different items numbered 0... N-1, where each item has a weight of W (an array of item weights) and a value of V (an array of item values). What items can be placed in the backpack to maximize the total value of the items within the backpack's capacity?Copy the code

Here’s the logic:

Suppose you now have a backpack with capacity C = 5 and three items with an array of weights and values w = [1, 2, 3] and V = [6, 10, 12].

We define a two-dimensional array dp with the number of items on the X-axis and backpack capacity on the Y-axis. Dp [I][j] represents the maximum value of items in the backpack when the number of items in the backpack is I + 1 and the backpack capacity is J. The initial dp value is -1, as follows:

The length of y axis is backpack capacity + 1, which is convenient for subsequent calculation

We assign a value to the first row, and when the capacity is 1, we can drop the first element, and store the value of that element in dp, which is 6.

And then we assign the second row, because the weight of the second element is 2, so by 2, there are three cases. [I][J]

• When the capacity is less than 2, it won’t fit, so pressdp[i-1][j]The value of the.
• When the capacity is greater than or equal to 2, takedp[i-1][j]andv[i] + dp[i - 1][c - w[i]]Compare, take the larger value. To compareDo not use the maximum value of the current elementAs well asCurrent element value + (capacity - current element weight) maximum value.

And then finally I assign the third row, same rule, and I get

The value represented by DP [2][5] is the maximum value required in our question. However, we can also optimize for spatial complexity, since only the elements above and to the left of the previous row are used for assignment of the two-dimensional array DP, so we can optimize for a one-dimensional array, assigning dp from right to left after initializing dp[0].

The solution of the classic 0-1 knapsack problem:

// This example optimizes the space complexity by optimizing the two-dimensional array into a one-dimensional array
const knapsack01 = (w, v, c) = > {
    let len = w.length;
    if (len === 0) return 0;
    let memo = new Array(c + 1).fill(0);
    for (let i = 0; i <= c; i ++) {
        if (i >= w[0]) memo[i] = v[0];
    }

    for (let i = 1; i < len; i ++) {
        for (let j = c; j >= w[i]; j --) {
            memo[j] = Math.max(memo[j], v[i] + memo[j - w[i]]); }}return memo[c];
}
Copy the code

This is the most basic knapsack problem, students who have studied dynamic programming should be able to solve it.

Summary of several knapsack problem basic solution method

There are several common knapsack problems, and I’ll start by listing their basic loop logic and their core state transition equations. In the following sections, I’ll list a very classic example of some of these common backpack problems in practice.

Features of common backpack problems:

You’re given an array of nums, and you’re given a target value, and you’re asked how many elements from nums can satisfy target?

Circular logic

Class 0-1 knapsack problem

Nums data can only be used once, and no sequential relationship is required

Nums loops (X-axis) are nested target loops (Y-axis), and target loops are in reverse orderCopy the code

Reusable backpack

Data in NUMS can be reused and does not require a sequential relationship

The NUMS loop (X-axis) is nested with the target loop (Y-axis) and the target loop is in positive orderCopy the code

Arrangement of backpack

The data in NUMS can be reused, but the order between the elements needs to be considered, and different orders represent different results.

Target loop (X-axis) nested NUMS loop (Y-axis), all in positive orderCopy the code

State transition equation

Number of questions

How many combinations, how many terms satisfy this condition

dp[i] += dp[i-num];
Copy the code

True and false questions

Verify that there is an item that satisfies the condition

dp[i] = dp[i] || dp[i-num];
Copy the code

Maximum and minimum problem

Find the maximum/minimum value that satisfies the condition

dp[i] = Math.max / min(dp[i], dp[i-num]+1);
Copy the code

Practice: a few classic examples

Combination sum 4

leetcode 377Give you an array of different integers, nums, and a target integer, target. Find and return the number of combinations of elements from nums that add up to target. The question data ensures that the answers match32Bit integer range. Enter: nums = [1.2.3], target = 4Output:7Explanation: All possible combinations are: (1.1.1.1)
(1.1.2)
(1.2.1)
(1.3)
(2.1.1)
(2.2)
(3.1Note that sequences of different orders are treated as different combinations.Copy the code

Let’s first determine the cycle and the core state transition equation.

Because of the number of combinations taken, the core state transition equation is dp[I] += dp[i-num]

Belong to permutation knapsack, the result of different order is treated as different combination, so the loop mode is target loop nested NUMS loop, all order

Let’s confirm the definition of dp. Dp [I][j] represents the number of element combinations that can satisfy the sum of target when the target value is j and I elements are taken out from NUMS.

var combinationSum4 = function(nums, target) {
    // A two-dimensional array is optimized to a one-dimensional array
    // Set the length to target + 1 to handle target = 0
    const dp = new Array(target + 1).fill(0);
    // initialize dp[0][j], when 0 elements are used, and target is 0, there is a combination number, so 1
    dp[0] = 1;
    for (let i = 1; i <= target; i++) {
        for (const num of nums) {
            if (num <= i) {
                // Only if target is greater than the current num value can there be a combination of the current num itemsdp[i] += dp[i - num]; }}}return dp[target];
};
Copy the code

Change change

leetcode 322Given different denomination coins nums and a total amount target. Write a function to calculate the minimum number of coins needed to make up the total. If none of the coin combinations make up the total, return -1. You can think of an infinite number of each coin. Enter: nums = [1.2.5], target = 11Output:3Explanation:11 = 5 + 5 + 1Enter: nums = [2], target = 3Output: -1Enter: nums = [1], target = 0Output:0
Copy the code

The core state transition equation is dp[I] = math.min (dp[I], dp[i-num]+1);

Belong to repeatable knapsack, numS data can be reused, so the cycle mode is NUMS cycle nested target cycle, and the target cycle is positive order

Dp [I][j] can be defined when using the first 1,2, 3… Nums. length element, and target is j, the minimum number of coins that can make up the total amount

var coinChange = function(nums, target) {
    const len = nums.length;
    // Boundary condition processing
    if (len === 0) return target === 0 ? 0 : -1;
    const dp = new Array(target + 1).fill(Infinity);
    // initialize dp[0,1,2...target] when the X-axis is 0, that is, only the first element in nums is taken
    for (let i = 0; i <= target; i ++) {
        // If target is divisible by nums[0], set it to I/nums[0]
        // If target is 0, there can be a value of 0, indicating that 0 elements are taken
        if ((i % nums[0= = =])0) dp[i] = i / nums[0];
    }
    for (let i = 1; i < len; i ++) {
        // Positive traversal is required because elements in NUMs can be reused
        // For example, nums = [1, 2, 5], target = 11, when iterating through 5
        // target = 6, dp[6] will be updated
        // if amout = 11, the value of dp[11] is related to dp[6], but dp[6] has been updated
        // This implements the reuse of elements in nums
        for (let j = 1; j <= target; j ++) {
            if (j >= nums[i]) {
                // Core state transition equation
                dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1); }}}// Result processing
  const res = dp[target];
  return res === Infinity ? -1 : res;
}
Copy the code

Divide equal and subset

leetcode 416You are given a non-empty array nums containing only positive integers. Determine if you can split this array into two subsets so that the sum of the elements in the two subsets is equal. Enter: nums = [1.5.11.5] output:trueAn array can be split into [1.5.5] and [11]. Enter: nums = [1.2.3.5] output:falseAn array cannot be split into two elements and equal subsets.Copy the code

In this case, the data needs to be processed to make it conform to the form of the knapsack problem.

Because it’s divided into two subsets, we just need to see if we can pick n elements, and the sum is sum over 2.

Because of the conditions of determining whether there is a meet, so core state transfer equation for the dp [I] = dp [I] | | dp [I – num]

Is a class 0-1 knapbag problem, because numS data can only be used once, so the numS loop is nested target(i.e., sum/2) loop, and the target loop is in reverse order

Dp [I][j] represents whether there is a subset whose sum of values is equal to j when taking the elements in nums[0… I]

var canPartition = function(nums) {
    // Calculate sum / 2
    let sum = 0, len = nums.length;
    for (let i = 0; i < len; i ++) {
        sum = sum + nums[i];
    }
    if (sum % 2! = =0) return false;
    let target = sum / 2;
    // Create an array of target + 1 using target(sum / 2) as the capacity
    let dp = new Array(target + 1).fill(false);
    // dp[0][j] = nums[0
    // dp[I] is set to true when I = nums[0]
    for (let i = 0; i <= target; i ++) {
        dp[i] = (nums[0] === i);
    }
    // I represents the current nums[I] element
    // Apply the loop logic above
    for (let i = 1; i < len; i ++) {for (let j = target; j >= nums[i]; j --) {
            // Apply the core state transition equation abovedp[j] = dp[j] || dp[j - nums[i]]; }}return dp[target];
}
Copy the code

Summary and Suggestions

This paper summarizes some common knapsack problem solution methods (cyclic mode, state transition equation). In the backpack problem solving process, if the question type can be appropriate, it can be based on these methods to find the idea of solving the problem, for beginners, can improve a lot of problem solving efficiency.

Here I also need to explain that it is useless to simply memorize these methods. You must memorize them on the basis of understanding. Because these methods are only a very basic box, the definition of boundary cases, DP, loops and state transition equations will change according to different problems and conditions, so we have to modify the code logic according to specific scenarios.

And the backpack problem is certainly more than so several categories, it has many other varieties, such as multi-dimensional cost of the backpack problem, there are dependent backpack problem and so on. For these problems, we also need to extend these basic methods.

In short, there is only one way to become stronger, and many brush questions.

Thank you

Thank you for reading, and if this article helped you, please give it a thumbs up. Thanks!