“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”
preface
Today is the fourteenth installment in our dynamic Programming program on the backpack problem.
Today we will learn about “multi-dimensional backpacks” and complete an exercise on it.
In addition, AT the end of the article, I listed the related topics of the backpack problem that I sorted out.
I’ll cover the backpacks in a structured order (updated every few days to make sure you digest them).
You can try to do it first, and you are welcome to leave a message to me, you feel related to the backpack DP type topic ~
Topic describes
This is LeetCode ** “474. One and zero” **, the difficulty is Medium.
You are given an array of binary strings and a sum of two integers.
Find and return the size of the largest subset that has at most one sum.
A set is a subset of a set if all the elements of are also elements of.
Example 1:
Input: STRS = [" 10 ", "0001", "111001", "1", "0"], m = 5, n = 3 output: 4: The largest subset with at most five zeros and three ones is {"10","0001","1","0"}, so the answer is 4. Other smaller subsets that satisfy the meaning of the question include {"0001","1"} and {"10","1","0"}. {"111001"} does not satisfy the meaning of the question, because it contains four 1's and the value 3 is greater than n.Copy the codeExample 2:
Input: STRS = ["10", "0", "1"], m = 1, n = 1 Output: 2 Explanation: The largest subset is {"0", "1"}, so the answer is 2.Copy the codeTip:
-
1 <= strs.length <= 600
-
1 <= strs[i].length <= 100
-
STRS [I] consists only of ‘0’ and ‘1’
-
1 <= m, n <= 100
Fundamental analysis
The questions usually associated with the “backpack problem” test the ability to transform the original problem into a “backpack problem.”
Turning a problem into a “backpack problem” often requires abstractions of the concepts of “value” and “cost” from the title.
If this problem is abstracted as “the backpack problem”, it should be:
The value of each string is (the contribution to the answer is), and the cost of the selection is the sum of the quantities in that string.
They ask us what is the maximum value given that the number of PI is no more than, the number of PI is no more than zero.
Since each string can only be selected once, and the selection of each string corresponds to “value” and “cost”, the question is also “maximum value”.
(Multidimensional) 01 Backpack
With the basic analysis, we can directly apply the “state definition” of backpack 01:
Represents the “maximum value” (the value of each string) of the preceding item under the condition that the numeric capacity does not exceed.
With the “state definition” in place, the “transition equation” is also easy to derive:
Where the array records the number of occurrences in the string.
Code (for easy understanding, the processing of the first item is taken out separately, or you can not take out, just let the item subscript from the beginning, see) :
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
// Preprocess the number of 0s and 1s per character
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zero++;
} else {
one++;
}
}
cnt[i] = new int[]{zero, one};
}
// Only the first item is considered
int[][][] f = new int[len][m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[0][i][j] = (i >= cnt[0] [0] && j >= cnt[0] [1])?1 : 0; }}// Handle the remaining items considering the situation
for (int k = 1; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Do not select the KTH item
int a = f[k-1][i][j];
// Select the KTH item (if there are sufficient m and N quotas available)
int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0; f[k][i][j] = Math.max(a, b); }}}return f[len-1][m][n]; }}Copy the codeclass Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][][] f = new int[len + 1][m + 1][n + 1];
for (int k = 1; k <= len; k++) {
int zero = cnt[k - 1] [0], one = cnt[k - 1] [1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
int a = f[k - 1][i][j];
int b = (i >= zero && j >= one) ? f[k - 1][i - zero][j - one] + 1 : 0; f[k][i][j] = Math.max(a, b); }}}returnf[len][m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗ N)O(K * m * n)O(K ∗m∗n) to handle state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(k∗m∗n)O(K * m * n)O(k∗m∗n)
Scroll to the array
According to state transitions, updating the state of an item depends only on the state of the previous item.
Therefore, you can use a “scrolling array” approach to spatial optimization.
Code (for easy understanding, the processing of the first item is taken out separately, or you can not take out, just let the item subscript from the beginning, see) :
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
// Preprocess the number of 0s and 1s per character
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zero++;
} else {
one++;
}
}
cnt[i] = new int[]{zero, one};
}
// Only the first item is considered
// Change "Item Dimension" to 2
int[][][] f = new int[2][m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[0][i][j] = (i >= cnt[0] [0] && j >= cnt[0] [1])?1 : 0; }}// Handle the remaining items considering the situation
for (int k = 1; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Do not select the KTH item
// Change k-1 to (k-1)&1
int a = f[(k-1) &1][i][j];
// Select the KTH item (if there are sufficient m and N quotas available)
// Change k-1 to (k-1)&1
int b = (i >= zero && j >= one) ? f[(k-1) &1][i-zero][j-one] + 1 : 0;
f[k&1][i][j] = Math.max(a, b); }}}// Change len-1 to (len-1)&1
return f[(len-1) &1][m][n]; }}Copy the codeclass Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][][] f = new int[2][m + 1][n + 1];
for (int k = 1; k <= len; k++) {
int zero = cnt[k - 1] [0], one = cnt[k - 1] [1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
int a = f[(k-1) & 1][i][j];
int b = (i >= zero && j >= one) ? f[(k-1) & 1][i-zero][j-one] + 1 : 0;
f[k&1][i][j] = Math.max(a, b); }}}return f[len&1][m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗ N)O(K * m * n)O(K ∗m∗n) to handle state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(k∗m∗n)O(K * m * n)O(k∗m∗n)
One dimensional optimization
In fact, we can continue to optimize the space.
Looking at our “state transition equation” again, we find that it depends not only on the previous line, but also explicitly on the states that are smaller than and smaller than.
You can rely only on the “right above” cell in the “top row” and the “right to the left of the top row” cell.
The dependencies corresponding to the “plain 01 knapsack problem” are shown below:
Therefore, you can directly refer to the “01 Backpack space optimization” method: cancel the “item dimension”, and then adjust the traversal order of capacity.
Code:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
int zero = 0, one = 0;
for (char c : strs[i].toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][] f = new int[m + 1][n + 1];
for (int k = 0; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = m; i >= zero; i--) {
for (int j = n; j >= one; j--) {
f[i][j] = Math.max(f[i][j], f[i-zero][j-one] + 1); }}}returnf[m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗ N)O(K * m * n)O(K ∗m∗n) to handle state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(m∗n)O(m * n)O(m∗n)
conclusion
Today we learned the “multidimensional backpack” problem, it is not difficult to find the “multidimensional backpack” and “plain traditional backpack” problem there is no essential difference.
We still adopt the basic idea of “traversing items – traversing capacity (multidimensional) – traversing decision”.
So the so-called “multi-dimensional backpack” problem is actually just the “traditional backpack” problem expansion.
The difficulty lies in the abstraction of “cost” and “value”.
After clarifying the “cost” and “value”, it can be fine-tuned according to the status definition of “01 backpack” or “full backpack” according to the choice of “one” or “multiple” items for each item.
Backpack Problems (Catalogue)
- Knapsack: Knapsack problem Lecture 1
- 01 Backpack: Backpack Problem, Lecture 2
-
01 Backpack: Backpack Problem Lecture 3
-
Complete knapsack: Knapsack problem Module 4
-
The complete backpack: The Backpack Problem Lecture 5
-
【 exercise 】 Complete backpack: Backpack problem Lecture 6
-
【 Exercise 】 Complete backpack: Backpack problem Module 7
-
Multiple backpacks: Module 8 of the backpacks problem
-
Multiple backpacks (Optimization)
-
【 on 】 multiple backpack (optimization) : backpack problem ninth
-
【 next 】 multiple backpack (optimization) : backpack problem ten
-
Hybrid knapsack: Knapsack problem Module 11
-
Group backpack: Backpack problem module 12
- 【 exercise 】 Group backpack: Backpack problem module 13
- Multidimensional knapsack: Knapsack problem Module 14
- 【 exercise 】 Multi-dimensional backpack
- The tree backpack
- 【 exercise 】 Tree backpack
- Backpack for the number of schemes
- 【 Exercise 】 backpack for the number of schemes
- Backpack for specific plans
- 【 exercise 】 backpack for specific plans
- Generalization backpack
- 【 exercise 】 To generalize the backpack
The last
This is article No.474 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.