This is the 13th day of my participation in Gwen Challenge
Backpack DP
Backpack DP, the name actually comes from a more classic DP question: “backpack question”, in the interview is better known as “backpack nine.” But “backpack nine lectures” for many students who only need to attend an interview, the content is a bit difficult, and most interviews will only involve 01 backpack and complete backpack. So, I’m going to take you through an analysis of the frequent backpack question that comes up in job interviews.
If you haven’t studied the backpack problem, or even never heard of it, it doesn’t affect the rest of your study.
Example: split equal and subset
The title
A non-empty array containing only positive integers. Is it possible to split this array into two subsets so that the sum of the elements in the two subsets is equal?
Note: 1) There are no more than 100 elements in each array; 2) The size of the array cannot exceed 200
Input: A = [2, 2]
Output: true,
Explanation: This array can be divided into [2], and the sum of the two subsets [2] is equal.
Analysis of the
Since the sum of the two subsets is equal, if the sum of the entire array is odd, there is no need to discuss it. We’re only talking about the case where sum of A is equal to 2 x V. The sum of these two subsets is V.
The problem can also be imagined as:
Given A backpack of capacity V, you are given some rocks, the size of which is in array A[]. Now you need to pick up some rocks to fill the backpack of capacity V. (You don’t have to worry about filling the gap)
So, in this scenario, there are only two choices for each rock: select or not select. Let’s take a look at how to use the six-step method to solve this problem.
1. Last step
In this question, the more difficult to think of is the last step, let’s first explain the context of the last step.
First, assume that the array A[] = {1, 2, 3} is given, and then see what numbers can be combined using this array. At the beginning, if we didn’t take anything, we could definitely go to 0. Therefore, 0 can be set as the starting point.
At this point, you should have figured out what the final step should be. It depends on two things:
- The point set X that can be accessed (hereafter we call the number that can be accessed as point set);
- A [n – 1) elements.
The last step can be expressed in pseudocode as follows (resolved in comments) :
Y = {.... };// The state of the old point set
Z = new HashSet(Y); // A new set of accessible points
// Generate new accessible points
for node in Y:
Z.insert(node + A[n-1])
// check whether V is concentrated at N
Z.contains(V) -> true / falseThe relationship between the two point sets can be briefly expressed as follows:Copy the code2. The problem of child
By observing the last step, it can be found that it is to generate point set Z by adding edge A[n-1] on the basis of accessible point set Y. If we introduce an earlier set of accessible points X,
Its subproblem is:
Is it possible to access y1 in A set of accessible points X by adding A[I] element? Can I access y2? ... Can I access YM?Copy the code3. Recursive relationships
If we use f() function to represent this layer of relationship, it can be expressed as:
- f(X, A[n-2]) => Y
- f(Y, A[n-1]) => Z
Note that the f() function does not indicate whether a number can be generated; its output represents a set of points. So the lesson of this example is that sometimes the output of f(x) is not directly related to what we want.
For example, in this case, the answer we ultimately want is:
Does the value V appear in point set Z?
However, the f() function does not answer this question directly, but instead answers the final question in the following way:
f(Y, A[n-1]) => Z
return Z.contains(V)
Copy the code4. Representation of f(x)
In this case, the f() function is more commonly written as f(S, A[I]). Where S is the known set of points, and the output of this function is a new set of points.
So, when we write programs, what should we use to express the f() function? In the previous code, we used either arrays or hash functions. But in this case, S is the set of points that can be accessed. Like this, how do I hash?
Optimization of 1
However, if we follow the example given in the previous array A[] = {1, 2, 3}, we can use the f() function as follows:
S0 = {0}
S1 = f(S0, A[0])
S2 = f(S1, A[1])
S3 = f(S2, A[2])
return S3.contains(V)
Copy the codeWe found that this step can be easily written as a two-point set iteration:
old = {0}
for x in A:
new = f(old, x)
old = new
return old.contains(V)
Copy the codeOptimization of 2
Although only two point set iterations can complete the calculation process. However, we still have one condition that we don’t use, which is that the elements in the given array are all positive integers.
This means that when f(S, A[I]) iterates, the newly generated number is bound to be larger. How does this help with our iteration? Does this incremental direction allow us to get the job done with just one set?
Assuming S = {0, 5}, A[I] = 2 and now to iterate over A set in place, we start from small to large,
However, if you do this, you will get an error. Because A[I] = 2 is used twice, and they say it can only be used once.
The reason for this problem is that we can’t distinguish between old numbers and new ones. Using another array to mark the old number, the newly generated number is essentially indistinguishable from the two sets that complete the iteration. So what can help us distinguish between old numbers and new ones?
What if we try to update from large to small? Updating from large to small is based on the following condition:
The new number is always going to be bigger. If we add A[I] to the larger numbers first, the larger numbers will come later, and again, we will never encounter these new numbers.
We found that if we iterate from large to small, we can iterate with a set of points.
5. Initial conditions and boundaries
First of all, when we pick nothing, we definitely get 0, so the initial set of points is {0}.
And then the number we want to get is V. If you have some old set of points that are bigger than V, like R, you can just throw away R. Because A[I] is always positive in subsequent iterations, it only makes R bigger and bigger after iteration, so it makes no sense to keep R.
So the boundary of dynamic programming is [0, V].
6. Compute the order
There are two order of calculation to note:
When iterating, use A[0], A[1]… , A[n-1] updates the point set in turn;
When we update the set of points, we need to update them in order of largest to smallest.
A Boolean array can be used to represent a set of points when f() only needs one set of points for the entire iteration, and the range of points is fixed [0, V].
The complete code
After the previous analysis, we can write the following code (parsing in the comments) :
class Solution {
public boolean canPartition(int[] A) {
final int N = A == null ? 0 : A.length;
if (N <= 0) {
return true;
}
// Array summation
int s = 0;
for (int x : A) {
s += x;
}
// If it is odd, there is no way to cut it
if ((s & 0x01) = =1) {
return false;
}
// Divide into equal sum, then equivalent to take half of the same value
final int V = s >> 1;
// This dp represents the set of points that can be accessed initially
// We use true to indicate that the point exists in the point set
// false indicates that this point does not exist in the point set
boolean[] dp = new boolean[V + 1];
S0 ={0}
dp[0] = true;
// start with a[I]
for (int x : A) {
// Notice the direction of the update here
for (int node = V; node - x >= 0; node--) {
final int newNode = node;
final int oldExistsNode = node - x;
if (dp[oldExistsNode]) {
dp[newNode] = true; }}}returndp[V]; }}Copy the codeComplexity analysis: time complexity O(NV), space complexity O(V).
summary
In this problem, we once again use the 6-step analysis method of DP to solve the problem. In the process of solving, two interesting points can be found:
- A[I] is used for gradual iteration;
- The main reason why dp[] needs to be updated from large to small is that the numbers in the array are all positive integers.