Full Resolution of Knapsack Problem

takeaway

Knapsack Problem is a very classic type of dynamic programming. The general solution idea is as follows: the maximum total value of items in the state before I can be loaded under the backpack with capacity J, and then the capacity of items and backpack is traversed, and the current state is constantly updated according to the previous state. But there are still a lot of details, like

1. What is the time complexity of the knapsack problem (note that the knapsack problem is NP complete)?
2. How do I do state compression?
3. The order of the double cycle problem, why must be the first cycle items, after the cycle capacity?
4. How to solve the problem when the capacity of the backpack is very large (larger than the upper limit of the array memory can be allocated)?
5. Some variations on the backpack problem

This paper analyzes 12 classic knapsack problems and their variants, as well as some problems solved by knapsack problem ideas in Leetcode. Due to space limitations, it is divided into two parts. The next

Introduction to backpack Problem

The description of Knapsack Problem is usually as follows: given some items, each item has its own weight, price and other attributes, it is necessary to select which items to put into a backpack with a fixed capacity, so that the total price can be the highest. In addition to the basic description, some restrictions may be added, such as the number of items per item. Backpack problems can be divided into three categories: 0-1 backpack, multiple backpack, complete backpack. 0-1 backpack refers to each item can only put 0 or 1 into the backpack; Multiple backpacks give a maximum number of items per item, as long as each item does not exceed its own limit; Complete backpack is an unlimited number of items, you can take any number. Note that knapsacks are NP-complete, and why we can provide dynamic programming solutions with polynomial time complexity will be discussed in more detail later. Such problems are often referred to as pseudo-polynomial time algorithms.

12 exercises

Backpack problem: Given some items can be packed into a backpack, how full can it be? Assume the backpack capacity is M and each item is A[I] in size.

This question can only choose to pack or not pack each item, is a typical 0-1 backpack problem, even the price of items are saved. Let’s start with the most basic dynamic programming solution. The core of dynamic programming solution is state definition and transition equation. Almost all states of knapsack problems can be defined as:

For the first I items, how much can be filled with the backpack capacity of J/what is the maximum price of the bag /… Other goals that need to be maximized.

In this problem, we can define the current state dp[I][j] as the maximum weight that can be carried in a backpack of capacity J. Notice that this is the pre-i item, so the item we’re dealing with is subscript i-1 and weighs A[i-1], and notice that in all backpack problems, we use the pre-I item instead of the i-i item to represent the state, because the 0 item doesn’t represent the empty backpack.

Next, consider the transfer equation. For the current item **(subscript i-1)**, we can only put it or not put it. If we do not put it in the backpack, then the state of the former I item is the same as that of the former I-1 item, that is, DP [I][j] = DP [i-1][j]. If the item is loaded, since the backpack has already taken up the weight of A[i-1], we are looking for the maximum load under the remaining capacity, which is DP [I-1][J-A [I]]. Thus, we get the transfer equation:

dp[i][j] = Max(dp[i-1][j], dp[i-1][j-A[i-1]]+A[i-1])
Copy the code

Dp [I][j] = dp[i-1][j] = dp[i-1]

Finally consider the boundary condition, dp[?] [0] indicates that in the backpack with capacity 0, dp[?] [0] should be 0. Similarly, dp[0][?] Represents the first 0 items into the backpack, obviously also 0. So our cycle index can start at 1. Here’s the code:

/** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ const backPack = function (m, A) { let n = A.length; let dp = Array(n + 1).fill().map(() => Array(m + 1).fill(0)); // Open a two-dimensional array of size n+1 * m+1 i <= n; i++) { for (let j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; / / first direct assignment for dp [j] [I - 1] if (A < = j [I - 1]) {dp [I] [j] = math.h Max (dp [I] [j], dp [I - 1] [I - 1]] [j - A + A] [I - 1); } } } return dp[n][m]; };Copy the code

An aside:

For 2d Array initialization in javascript, the new keyword for new Array can be omitted, and map is used to prevent per-row Array reference problems.

Unfortunately, this solution exceeds the memory limit

Notice that in our transfer equation, the state of dp[I][j] is only the same as that of DP [i-1][? Therefore, we can compress the dimension of the first I items. The scrolling array can compress the space to 2 * (m+1). A very simple state compression strategy is to use a 2 * (m+1) two-dimensional array with modulo 2. The code is as follows:

const backPack = function (m, A) { let n = A.length; let dp = Array(2).fill().map(() => Array(m + 1).fill(0)); For (let I = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { dp[i % 2][j] = dp[(i - 1) % 2][j]; if (A[i - 1] <= j) { dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + A[i - 1]); } } } return dp[n % 2][m]; };Copy the code

This compression changes the first code simply by changing the initialization size of the DP array and setting the values of each dp[I][?] , dp[i-1][?] Add a %2 to the end of the I, no memory burden.

Note that we only rely on the state array of the first i-1 item when calculating the state of the first I-1 item, and j always depends on A smaller value, dp[I][j] depends on dp[i-1][j-a [i-1]], where J-a [i-1] is always less than j. If we were to iterate through the weight in reverse order, wouldn’t we be able to compress the state array into one dimension? The state f[j] here represents the maximum capacity that can be filled with j. The following code

const backPack = function (m, A) { let n = A.length; let f = Array(m + 1).fill(0); for (let i = 1; i <= n; i++) { for (let j = m; j >= A[i - 1]; J -) {/ / note that there is A reverse traversal f [j] = math.h Max (f [j], f [j - A [I - 1]] + [] I - 1 A). } } return f[m]; };Copy the code

Note that when traversing the weight in the code, we only traversed from m to A[i-1], because when j is less than A[i-1], there is no need to update the value of f[j], which is the same as if (A[i-1] <= j) in the previous code.

Here we explore two questions: 1. Why count items first and then weight? 2. Why is knapsack problem a pseudo-polynomial time complexity?

Question 1: Why count items first and weight later?

It can be tested first. Without state compression, the cyclic order in which items and weights are exchanged does not affect the correctness of the result, because dp[I][j] is only updated once for any state. For the solution that uses the state compression of the scrolling array, the loop order will be wrong once it is changed. Consider A simple example, m = 5, A = [1,1,1], cycle weight first, assume the current weight is 4, then cycle item (1 -> 3), since 1%2 = 3%2, update DP [1%2][4], then DP [3%2][4] will overwrite this value, when weight is 5, We want to calculate dp 2% [2] [5] = dp [(2, 1) % 2] [5 – A [1]] = dp 1% [2], [4], and this value has been before dp covering 3% [2] [4], and apparently have A dp [1] [4]. = dp[3][4], so there will be an error here. Of course, in real code, as long as you remember to always recycle items first and then recycle weights later, you won’t have a problem.

Question 2: Why is knapsack problem pseudo polynomial time complexity?

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input Largest integer present in the input — but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

Here we pick a Wiki, the definition of the underline parts, if the time complexity of the algorithm with the input values are polynomial, note that there is the value of input, rather than the size of the input to an array of length n, then its input size is n, but for a numeric value, it is only in the memory of the log (n) bits, That’s the size of its input. In the knapsack problem, the time complexity is m*n, where M is only log(m) in memory, so the real complexity should be exponential, so it is called pseudo polynomial time complexity.

125. Backpack problem II: Given some items that can fit into a backpack, what is the maximum value that can fit into a backpack? Assume that backpack capacity is M, each item is A[I] in size and V[I] in value.

The only difference between this question and the backpack question is that every item has value, and the maximum goal is the value that can be carried in the backpack. The definition of state is slightly changed, dp[I][j] represents the first I items, the maximum value that can be held when the backpack capacity is J, and the transfer equation is

dp[i][j] = Max(dp[i-1][j], dp[i-1][j-A[i-1]]+V[i-1])
Copy the code

Here we’re going to go straight to the code for state compression using a scroll array

const backPackII = function (m, A, V) {
    let n = A.length;
    let dp = Array(2).fill().map(() => Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j - A[i - 1] >= 0) {
                dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return dp[n % 2][m]
};
Copy the code

This problem can also be compressed into a one-dimensional array as follows. And notice that our outer loop directly uses I = 0 as the initial value and I < n as the loop termination condition, so we don’t need -1 to access the value and weight arrays.

const backPackII = function (m, A, V) {
    let n = A.length;
    let f = Array(m + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let j = m; j >= A[i]; j--) {
            f[j] = Math.max(f[j], f[j - A[i]] + V[i]);
        }
    }
    return f[m];
};
Copy the code

Backpack problem III: Given an infinite number of items that can fit into a backpack, what is the maximum value that can fit into a backpack? Assume that backpack capacity is M, each item size is A[I] and value is V[I].

This problem is known as the complete backpack problem, and the biggest difference from the 0-1 backpack is that you can take an infinite number of each item. The change in the title has no effect on the definition of state, dp[I][j] still represents the maximum load value of the first I items under a backpack of capacity J. For the current item, we can consider installing 0… K, until it exceeds the current backpack capacity j, which is k * A[I] <= j, so we can add another layer of loop to find out how many items we currently hold, and the transfer equation becomes:

dp[i][j] = Max(dp[i-1][j], dp[i-1][j-k*A[i-1]]+k*V[i-1])
Copy the code

Let’s start with the most basic version of stateless compression, as follows:

const backPackIII = function (A, V, m) { let n = A.length; let dp = Array(n + 1).fill().map(() => Array(m + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; For (let k = 0; A[i - 1] * k <= j; k++) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]); } } } return dp[n][m]; };Copy the code

Next, use the scroll array for state compression:

const backPackIII = function (A, V, m) {
    let n = A.length;
    let dp = Array(2).fill().map(() => Array(m + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            for (let k = 0; A[i - 1] * k <= j; k++) {
                dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - k * A[i - 1]] + k * V[i - 1]);
            }
        }
    }
    return dp[n % 2][m];
};
Copy the code

Can this problem also be reduced to one dimension? The answer is yes. The inner loop of knapsack problem II is changed from large to small to large, as shown below. The principle is very simple. Let the state f[j] represent the maximum amount of value that can be stored at capacity J. The transfer equation is:

f[j] = Max(f[j], f[j - A[i]] + V[i]);
Copy the code

The code is as follows, notice our inner loop, j only needs to start from A[I], thus eliminating the need to determine if j – A[I] is negative.

const backPackIII = function (A, V, m) {
    let n = A.length;
    let f = Array(m + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let j = A[i]; j <= m; j++) {
            f[j] = Math.max(f[j], f[j - A[i]] + V[i]);
        }
    }
    return f[m]
};
Copy the code

798. Backpack question VII: Given a number of items that can fit into a backpack, each item has a limited number, what is the maximum value that can fit into the backpack? Assume the backpack capacity is M, each item is A[I] in size, V[I] in value, and N[I] in quantity.

dp[i][j] = Max(dp[i-1][j], dp[i-1][j-k*A[i-1]]+k*V[i-1])
Copy the code

/**
 * @param n: the money of you
 * @param prices: the price of rice[i]
 * @param weight: the weight of rice[i]
 * @param amounts: the amount of rice[i]
 * @return: the maximum weight
 */
const backPackVII = function (n, prices, weights, amounts) {
    let numOfItems = prices.length;
    let dp = Array(numOfItems + 1).fill().map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= numOfItems; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            for (let k = 0; k <= amounts[i - 1] && k * prices[i - 1] <= j; k++) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * prices[i - 1]] + weights[i - 1] * k);
            }
        }
    }
    return dp[numOfItems][n];
};
Copy the code

const backPackVII = function (n, prices, weights, amounts) {
    let numOfItems = prices.length;
    let dp = Array(2).fill().map(() => Array(n + 1).fill(0));
    for (let i = 1; i <= numOfItems; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            for (let k = 0; k <= amounts[i - 1] && k * prices[i - 1] <= j; k++) {
                dp[i % 2][j] = Math.max(dp[i % 2][j], dp[(i - 1) % 2][j - k * prices[i - 1]] + weights[i - 1] * k);
            }
        }
    }
    return dp[numOfItems % 2][n];
};
Copy the code

const backPackVII = function (n, prices, weights, amounts) {
    let numOfItems = prices.length;
    let f = Array(n + 1).fill(0);
    for (let i = 0; i < numOfItems; i++) {
        for (let k = 1; k <= amounts[i]; k++) {
            for (let j = n; j >= prices[i]; j--) {
                f[j] = Math.max(f[j], f[j - prices[i]] + weights[i]);
            }
        }
    }
    return f[n];
};
Copy the code

562. Knapsack problem IV: Give n items and an array, nums[I] represents the size of the ith item, ensure that the size is positive and there are no duplicates, positive integer target represents the size of the backpack, find the number of schemes that can fill the backpack. Each item can be used countless times.

The goal of this problem is to find the number of ways to fill the backpack. There are many similar problems, such as climbing stairs. How many ways are there to reach the top when you can climb one or two steps at a time? Or if the robot goes from the top left corner of the grid to the bottom right corner, one grid to the right or one grid to the bottom right corner, how many ways can it get to the bottom right corner? Of course, there are some differences in detail between these two questions and this one, which we will also discuss later. In general, the state of the problem is how many ways there are to get to the current state. Back to the problem, note that the number of options required to fill the backpack is 3 and the weight of the item is [1,2], then [1,2], [2,1] is only one option. Here we define the state dp[I][j] to represent the previous I items. Under the backpack of capacity J, there are several schemes. We are calculating dp[I +1][?] As item A[I] is newly added, there will be no repetition of [1,2], [2,1]. Then we consider the transition equation, which is very simple, how many states can be transferred to dp[I][j], so dp[I][j] should be what, which is how many options there are. In addition, since there is no limit to the number of items per item, we also need the number of items in circulation k.

dp[i][j] += dp[i-1][j-k*nums[i-1]];
Copy the code

This problem also needs to consider some additional boundary cases. According to the transfer equation above, if the previous state value is 0, then the current state will not add, so we must assign 1 to all cases dp[I][0], which indicates that there is a solution for the backpack capacity of 0. Conversely, dp[0][j] means that 0 items fill the backpack with capacity J. Since the number of items is 0, it cannot be filled, so dp[0][j] should be 0. The code is as follows:

const backPackIV = function (nums, target) {
    let n = nums.length;
    let dp = Array(n + 1).fill().map(() => Array(target + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 1; i <= n; i++) {
        dp[i][0] = 1;
        for (let j = 1; j <= target; j++) {
            for (let k = 0; k * nums[i - 1] <= j; k++) {
                dp[i][j] += dp[i - 1][j - k * nums[i - 1]];
            }
        }
    }
    return dp[n][target];
};
Copy the code

At the beginning of each loop item, the array containing the current state must be reset to 0, with the first digit set to 1. Refer to the version of stateless compression, dp[I][?]. The initial value of is 0, and its value is derived only from the total number of previously transferable states.

const backPackIV = function (nums, target) { let n = nums.length; let dp = Array(2).fill().map(() => Array(target + 1).fill(0)); dp[0][0] = 1; for (let i = 1; i <= n; i++) { dp[i % 2].fill(0); Dp [I % 2][0] = 1; for (let j = 1; j <= target; j++) { for (let k = 0; k * nums[i - 1] <= j; k++) { dp[i % 2][j] += dp[(i - 1) % 2][j - k * nums[i - 1]]; } } } return dp[n % 2][target]; };Copy the code

Further, try to compress to a one-dimensional array. We don’t care how many items each state contains, just add the number of options for the previous state, and since items loop through the outer layer, there is no repetition of [1,2], [2,1]. The code is as follows:

const backPackIV = function (nums, target) { let f = Array(target+1).fill(0); f[0] = 1; for(let n of nums){ for(let i=n; i<=target; i++){ f[i] += f[i-n]; } } return f[target] }Copy the code

564. Knapsack problem VI (Combined summation) : Give an array NUMs of all positive integers with no duplicates. Find all combinations from which the sum is target. Note that a number can appear multiple times in a combination, and different sequences of numbers are considered as different combinations.

Notice that in the problem, the order of the numbers is considered to be a different combination (more specifically, it’s a permutations problem), so we can’t do what we did to avoid repeating by recycling items first. Instead, we should do the opposite: recycle the backpack first, recycle the items, In this way, we can satisfy the requirement in the question that “different order of numbers is considered to be different combinations”. At this point, the state definition does not need the dimension of the previous I items, but only needs a one-dimensional array f, where f[I] represents the number of combinations that exactly fill capacity I. The transfer equation is:

f[i] += f[i - nums[j]]
Copy the code

The code is as follows:

const backPackVI = function (nums, target) { let f = Array(target + 1).fill(0); f[0] = 1; For (let I = 0; for (let I = 0; i <= target; If (I >= n) {f[I] += f[i-n]; if (I >= n) {f[I] += f[i-n]; } } } return f[target]; };Copy the code

Backpack problem V: Given that some items can be loaded into a backpack and each item can only be used once, how many scenarios can fill the backpack? Assume that the backpack capacity is M and each item size is A[I].

In this problem, each item can only be used once, so we still need to use DP [I][j] to represent the number of items before I. In the case of capacity j, how many items can be held to avoid repeating problems. The transfer equation is:

dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]]; 
Copy the code

Dp [i-1][j] indicates not to put the item, dp[i-1][j-nums [i-1]] indicates to put the current item. Here we directly put the state compression version of the scroll array code. Here we do not reset the current array to all zeros at the start of each loop because dp[I % 2][j] = dp[(I – 1) % 2][j] directly assigns the current state to the previous state and 0 is redundant.

const backPackV = function (nums, target) {
    let n = nums.length;
    let dp = Array(2).fill().map(() => Array(target + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        dp[i % 2][0] = 1;
        for (let j = 1; j <= target; j++) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j - nums[i - 1] >= 0) {
                dp[i % 2][j] += dp[(i - 1) % 2][j - nums[i - 1]];
            }
        }
    }
    return dp[n % 2][target];
};
Copy the code

And then we’re going to compress it down to one dimension, again going back to front.

const backPackV = function (nums, target) {
    let n = nums.length;
    let f = Array(target + 1).fill(0);
    f[0] = 1;
    for (let i = 0; i < n; i++) {
        for (let j = target; j >= nums[i]; j--) {
            f[j] += f[j - nums[i]];
        }
    }
    return f[target];
};
Copy the code

799. Backpack question VIII: Give some coins of different value and number. Find out how many values these coins can combine in a range from 1 to n. Each coin is value[I] and each coin is amount[I].

Just to clarify, in this problem, “find the number of coins that can be combined in the range of 1 to n,” means how many of these numbers, 1 to n, can be combined with these coins. Our previous DP array was to find the number of ways to fill the backpack with capacity J for the first I items. Then we take the total value of 1~n as the backpack capacity and count how many 1~n capacities there are. There is at least one way, which is the result we want. To simplify things a little bit more, our DP array just needs to store whether it can fit or not, and we don’t care how many ways it can fill the current capacity. Therefore, the defined state DP [I][j] represents whether the backpack with capacity J can be filled with the first I items, and the transfer equation is:

dp[i][j] |= dp[i-1][j - k * value[i-1]]
Copy the code

Where k represents the number of items currently taken, k must meet k <= amount[i-1] and k * amount[i-1] <= j. When initializing, you can set dp directly. [0] = true.

const backPackVIII = function (n, value, amount) { let numOfItems = value.length; let dp = Array(numOfItems + 1).fill().map(() => Array(n + 1).fill(false)); for (let i = 0; i <= numOfItems; i++) { dp[i][0] = true; } for (let i = 1; i <= numOfItems; i++) { for (let j = 1; j <= n; j++) { for (let k = 0; k <= amount[i - 1] && j >= k * value[i - 1]; K++) {/ / note that we use here is | = or equal to, as long as there is a state in front to true enough dp [I] [j] | = dp [I - 1] [j - k * value [I - 1]]. } } } let count = 0; for (let i = 1; i <= n; i++) { if (dp[numOfItems][i]) { count++; } } return count; }Copy the code

However, this version of the solution times out, as does the solution using a scrolling array for state compression. We can roughly estimate the time complexity of the current algorithm as O(numOfItemsnamount), where amount can be assumed to be the average amount of each item. The idea in knapsack problem VII is to expand items as if they were 0-1 knapsack problems, but the time complexity is not reduced and the amount is still needed for each iteration. The correct solution is to introduce an array that specifically calculates how many current items are used to form j, with no update if the number exceeds the upper limit. The size of the count array is n+1, and the element of the array tells us how many items are currently used to make up this capacity, and as we walk through the items, we have to reopen the count array every time we add a new item. Count [j-value [I]] must be strictly less than amount[I], which means that at least one more item can be loaded. By introducing the count array, we eliminate the need to traverse the number of items dimension, greatly reducing time complexity.

const backPackVIII = function (n, value, amount) { let numOfItems = value.length; let f = Array(n + 1).fill(false); f[0] = true; let res = 0; for (let i = 0; i < numOfItems; i++) { let count = Array(n + 1).fill(0); for (let j = value[i]; j <= n; j++) { if (! f[j] && f[j - value[i]] && count[j - value[i]] < amount[i]) { f[j] = true; res++; count[j] = count[j - value[i]] + 1; } } } return res; };Copy the code

IX: You have A total of N thousand yuan and want to apply to foreign universities. If you want to apply, you need to pay a certain application fee. Give the application fee of each university and the probability of your getting an offer from this university. If you can afford it, you can apply to multiple universities. Find the highest likelihood of getting at least one offer. There is a total of N thousand yuan. The prices array represents the application fee of each university, and probability represents the admission probability of each university.

The question requires the highest possibility of getting at least one offer, so we just need to calculate the probability of failing to apply for any offer and subtract 1 from the probability of at least one offer. In the pre-processing, we can first convert all the probabilities into the probability of failing to apply for any offer. We regard N million yuan as the backpack capacity, and the application fee as the weight of each item. Compared with the traditional backpack problem, the goal of the traditional backpack problem is to seek the maximum value, but we just change the maximum probability here. And since a college only needs to apply once, this is a classic 0-1 backpack problem. The definition state DP [I][j] represents the maximum probability of getting at least one offer from I schools before the application, which costs J million yuan. The transfer equation is as follows

dp[i][j] = max(dp[i][j], 1 - (1 - dp[i-1][j-prices[i-1]]) * (1 - probability[i-1]))
Copy the code

Dp [i-1][J-prices [i-1]] represents the maximum probability of receiving at least one offer. We first subtract it from 1 to obtain the probability of receiving no offer, and then multiply it by 1-probability [i-1] to obtain the first I schools. The probability of not getting a single offer, and then subtract it by 1. The transfer equation is a little bit more complicated, but we can actually change the goal to a minimum probability that no school can get, and at the end of the return, we can just subtract 1. All probabilities were preprocessed into 1-probability [I], and it was assumed that the new probability of failure to apply was noProbability. The new state DP [I][J] can be defined as the minimum probability of failing to apply for any of the former I schools, which costs J million yuan. The transfer equation is as follows:

dp[i][j] = min(dp[i][j], dp[i-1][j-prices[i-1]]*noProbability[i-1])
Copy the code

The code is as follows:

const backpackIX = function (n, prices, probability) {
    let numOfItems = prices.length;
    let dp = Array(numOfItems + 1).fill().map(() => Array(n + 1).fill(1));
    let noProbability = probability.map(p => 1 - p);
    for (let i = 1; i <= numOfItems; i++) {
        for (let j = 0; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= prices[i - 1]) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - prices[i - 1]] * noProbability[i - 1]);
            }
        }
    }
    return 1 - dp[numOfItems][n];
};
Copy the code

Copy the previous state compression method, compress into a one-dimensional array:

const backpackIX = function (n, prices, probability) {
    let dp = Array(n + 1).fill(1);
    for (let i = 0; i < probability.length; i++) {
        probability[i] = 1 - probability[i];
    }

    for (let i = 0; i < probability.length; i++) {
        for (let j = n; j >= prices[i]; j--) {
            dp[j] = Math.min(dp[j], dp[j - prices[i]] * probability[i]);
        }
    }
    return 1 - dp[n];
};
Copy the code

X: You have a total of N yuan, and the merchant has three kinds of goods, the price of which is 150 yuan, 250 yuan and 350 yuan respectively. The quantity of these three goods can be considered as unlimited. After purchasing the goods, you need to give the remaining money to the merchant as a tip.

Another way of saying this is how full the backpack can be, and then subtracting the maximum from the total capacity of the backpack is the minimum tip left for the merchant. The code is as follows:

const backPackX = function (n) { let prices = [150, 250, 350]; // let f = Array(n + 1).fill(0); for (let i = 0; i <= n; i++) { for (let p of prices) { if (i - p >= 0) { f[i] = Math.max(f[i], f[i - p] + p); } } } return n - f[n]; };Copy the code

971. Surplus value backpack: There is a backpack of capacity C. There are n category A items, the volume of the ith Category A item is A [I], and the value of the item is the remaining backpack capacity after loading the item * K1. There are m category B items, the volume of the ith Category B item is B [I], and the value of the item is the remaining capacity of the backpack after loading the item * K2. Get the maximum value you can get.

Notice that when we load items, we always load small items first, so as to make the remaining volume as large as possible and thus get the highest value. So we first sort the items, from small to large. In addition, for category A items, when we take the I item, we must have already taken the 0 ~ I – 1 item, because the volume of the item in front is always smaller than the current one, so it will inevitably be taken. Therefore, when calculating the residual value, prefix and array can be used to optimize the calculation result, represented by SA and sb. When dp[I][j] is used to represent the first I items of class A and the first J items of class B, the maximum residual value can be obtained, so the transfer equation is as follows. Note that the residual capacity is c-sa [I] -sb [j] whether it is transferred from the state dp[i-1][j] or DP [I][J-1].

dp[i][j] = Math.max(dp[i-1][j] + (c - sa[i] - sb[j]) * k1, 
                    dp[i][j - 1] + (c - sa[i] - sb[j]) * k2)
Copy the code

The implementation code is as follows

const getMaxValue = function (k1, k2, c, n, m, a, b) { let dp = Array(n + 1).fill().map(() => Array(n + 1).fill(0)); (x, y) => x - y); (x, y) => x - y); b.sort((x, y) => x - y); // let sa = Array(n + 1).fill(0); let sb = Array(m + 1).fill(0); for (let i = 0; i < n; i++) { sa[i + 1] = a[i] + sa[i]; } for (let i = 0; i < m; i++) { sb[i + 1] = b[i] + sb[i]; } let ans = 0; for (let i = 0; i <= n; i++) { for (let j = 0; j <= m; j++) { if (i + j > 0 && sa[i] + sb[j] <= c) { dp[i][j] = 0; if (i > 0) { dp[i][j] = dp[i - 1][j] + (c - sa[i] - sb[j]) * k1; } if (j > 0) { dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + (c - sa[i] - sb[j]) * k2); } ans = Math.max(ans, dp[i][j]); } } } return ans; };Copy the code

1382. Large backpack: Given a backpack capacity S, give n items, the value of the ith item is vi, the volume of the ith item is CI, ask how many items of value can this backpack hold, output the maximum value. (Each item can only be used once), note that the capacity s may be very large, but the number of items will be small. 1 <= S, vi, CI <= 10^13, 1 <= n <= 31.

To open a DP array in a normal way, we need at least one one-dimensional array, the size of the backpack, but the backpack can be up to 10^13, so it is obviously impossible to open the array directly. However, the maximum number of items is only 31. Of course, using DFS directly, enumerating each item to put or not to put is O(2^n). Consider using dichotomy to reduce time complexity. Divide the item into 2 piles, then enumerate all the combinations within the 2 piles, then iterate over all the combinations in one pile, and use dichotomy to find the two combinations with the highest total value in the other pile. This reduces the total time to O(2^ n/2) log(2^n/2), which is what the test data is stuck at. In addition to the general direction, there are some details worth considering. To use dichotomy, we have to sort our data. For each combination, we use [a,b], where A represents the total volume of the combination and b represents the total value of the combination. We can arrange them in order of size from small to large, or if the volume is the same, in order of value. Based on this sorted array, we can first do a filter, for the large, small value of the combination, directly discard. Let’s explain the code in sections.

First, divide all items into leftPart and rightPart arrays. The elements in the array are [vi, CI].

const getMaxValue = function (s, v, c) {
    let leftPart = [];
    let n = v.length;
    // [c[i],v[i]]
    for (let i = 0; i < Math.floor(n / 2); i++) {
        leftPart.push([c.shift(), v.shift()]);
    }
    let rightPart = v.map((item, index) => [c[index], v[index]]);
    // ... 
}
Copy the code

Then generate all combinations of the items, using the most conventional DFS.

// index: current index in arR array // curV: current total value // curC: current total volume // s: Const DFS = function (arr, res, index, curV, curC, s) {if (curC > s) {// If (curC > s) { return; } if (index === arr.length) {// add res.push([curC, curV]); return; } let [c, v] = arr[index]; dfs(arr, res, index + 1, curV, curC, s); DFS (arr, res, index + 1, curV + v, curC + c, s); // Get the current item};Copy the code

The combs array looks like this: [[0,0],[3,4]…] Combs [I][0] is the total volume of the i-th combination, combs[I][1] is the total value of the i-th combination. Notice that the combs array is sorted. The sorting rule is from small to large in size and from small to large in value. During traversal, maxV is used to maintain the maximum value of the traversal combination. If the value of the current combination is less than the maximum value, it means that the current combination is large and of low value and should be discarded directly.

const filterCombs = function (combs) {
    let res = [];
    let maxV = -1;
    for (let comb of combs) {
        if (comb[1] > maxV) {
            res.push(comb);
        }
        maxV = Math.max(maxV, comb[1]);
    }
    return res;
};
Copy the code

The core part of binary search is that the two combinations with the largest total value are filteredLeftCombs. FilteredRightCombs are filtered and sorted combinations. If you iterate through filteredRightCombs, subtract the volume of the current right-half combination from the total volume, which is the upper limit for the volume of the left half. Notice that the filtered combinations at this point have excluded all combinations with a large total volume but a small total value, so there must be a monotonically increasing relationship between the larger the total volume and the higher the value of the remaining combinations. So we just have to find the combination that has the largest total volume that is less than or equal to the upper bound on the volume of the left half. The binary lookup template here is easy to remember and will be covered in more detail in a later article.

/ /... let ans = 0; for (let i = 0; i < filteredRightCombs.length; i++) { let cap = s - filteredRightCombs[i][0]; If (cap > 0) {let l = 0; let r = filteredLeftCombs.length - 1; while (l + 1 < r) { let middle = Math.floor((l + r) / 2); if (filteredLeftCombs[middle][0] <= cap) { l = middle; } else { r = middle; } } if (filteredLeftCombs[r][0] <= cap) { ans = Math.max(ans, filteredLeftCombs[r][1] + filteredRightCombs[i][1]) } if (filteredLeftCombs[l][0] <= cap) { ans = Math.max(ans, filteredLeftCombs[l][1] + filteredRightCombs[i][1]) } } } return ans; }Copy the code

The complete code is as follows:

const dfs = function (arr, res, index, curV, curC, s) { if (curC > s) { return; } if (index === arr.length) { res.push([curC, curV]); return; } let [c, v] = arr[index]; dfs(arr, res, index + 1, curV, curC, s); dfs(arr, res, index + 1, curV + v, curC + c, s); }; const cmp = function (a, b) { if (a[0] === b[0]) { return a[1] - b[1]; } return a[0] - b[0]; }; const filterCombs = function (combs) { let res = []; let maxV = -1; for (let comb of combs) { if (comb[1] > maxV) { res.push(comb); } maxV = Math.max(maxV, comb[1]); } return res; }; Const getMaxValue = function (s, v, c) {let leftPart = []; const getMaxValue = function (s, v, c) {let leftPart = []; let n = v.length; // [c[i],v[i]] for (let i = 0; i < Math.floor(n / 2); i++) { leftPart.push([c.shift(), v.shift()]); } let rightPart = v.map((item, index) => [c[index], v[index]]); let leftCombs = []; dfs(leftPart, leftCombs, 0, 0, 0, s); let rightCombs = []; dfs(rightPart, rightCombs, 0, 0, 0, s); leftCombs.sort(cmp); rightCombs.sort(cmp); let filteredLeftCombs = filterCombs(leftCombs); let filteredRightCombs = filterCombs(rightCombs); let ans = 0; for (let i = 0; i < filteredRightCombs.length; i++) { let cap = s - filteredRightCombs[i][0]; if (cap > 0) { let l = 0; let r = filteredLeftCombs.length - 1; while (l + 1 < r) { let middle = Math.floor((l + r) / 2); if (filteredLeftCombs[middle][0] <= cap) { l = middle; } else { r = middle; } } if (filteredLeftCombs[r][0] <= cap) { ans = Math.max(ans, filteredLeftCombs[r][1] + filteredRightCombs[i][1]) } if (filteredLeftCombs[l][0] <= cap) { ans = Math.max(ans, filteredLeftCombs[l][1] + filteredRightCombs[i][1]) } } } return ans; };Copy the code

conclusion

Here are a few key points:

1. The knapsack problem always has an array of items that can be taken or not taken
2. The final result that needs to be optimized is the maximum value/maximum volume/weight, or a value related to the current value/volume/weight that needs to be converted by calculation. Or the number of solutions that satisfy a certain requirement.
3. There are generally two types of loops, one is the item loop, the item loop is generally in the outermost layer (except 564. Backpack problem VI), the second is the capacity cycle.
4. When you do state compression, you see if a variable in a dimension depends only on its state at i-1, and if it does, you can use a scrolling array to do state compression. To compress into one dimension, you often traverse backwards.

All topics and links

Ok,

1. 92. Backpack problem

2. 125. Backpack problem II

3. 440. Backpack problem III

4. 798. Backpack problem VII

5. 562. Backpack problem IV

6. 564. Sum of combinations IV

7. 563. Knapsack problem V

8. 799. \ [knapsack problem ix] (https://www.lintcode.com/problem/backpack-viii/description)

9. 800. \ [knapsack problem IX] (https://www.lintcode.com/problem/backpack-ix/description)
10. 801. \ [knapsack problem X] (https://www.lintcode.com/problem/backpack-x/description)

</div>
Copy the code

11. \ [971. Surplus value backpack] (https://www.lintcode.com/problem/surplus-value-backpack/description)

</div>
Copy the code

12. \ [1382. Large capacity backpack] (https://www.lintcode.com/problem/high-capacity-backpack/description)

The next

1. 322. Change

2. 474. One and zero

3. 494. The target and

4. 139. Word split