“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!”
Review three traditional backpack problems
So we’ve done the three traditional backpack problems.
Here are three more traditional backpacks:
-
01 Backpack: Emphasize that each item “can only be selected once”. “One-dimensional space optimization” cannot reduce the time complexity, and “traversal of capacity dimension” from “large to small” is required during “one-dimensional space optimization” **.
-
Full pack: Emphasize each item ** “unlimited selection”. “One-dimensional space optimization” is of mathematical significance, which can reduce the time complexity from to, and “traversal of capacity dimension from small to large” is required when “one-dimensional space optimization” is performed **.
-
Multiple packs: Emphasize that each item ** “can only be selected a limited number of times” **. Neither “one-dimensional space optimization” nor “general flattening” can reduce the time complexity, so additional optimization means should be applied: binary optimization or monotonous queue optimization.
The difficulty of the three kinds of backpack problems is “increasing”, but the importance is “decreasing” **.
Although “multiple knapsack” binary optimization and monotonous queue optimization are compared to Trick.
But “multiple backpacks” is not so common that I couldn’t find a title for “multiple backpacks” on LeetCode.
At the same time, the three kinds of backpack problems have ** “not more than” and “just” ** two state definitions.
The only difference between the two state definitions is “initialization.”
As for how to initialize, catch what states are legal:
-
For the status “Not exceeding” : All the values are valid.
Represents the maximum value achieved by the backpack capacity “not exceeding” without considering any item.
-
For the status definition of “just” : Only the valid value is in, and other values are invalid.
Represents the maximum value achieved when the backpack capacity is “exactly” without considering any item; Other capacities that “just don’t” have no valid value (because no item is considered).
In general, the three kinds of knapsack problems are so classical (combinatorial optimization problems in essence) that the “knapsack problem” directly becomes a kind of dynamic programming model.
My advice is to master all three packs. But if it comes down to prioritising, I’d rather you spend most of your time on “01 backpack” and “full backpack.”
Mixed backpack
Given item number and backpack capacity. The volume of the first item is, the value is, and the available quantity is:
-
This means that the item can only be used once
-
When represented the item can be used an unlimited number of times
-
If the value is any positive integer, it indicates the number available
Figure out which items can be loaded into the backpack so that the total cost of these items does not exceed the backpack capacity, and the total value of the largest.
Fundamental analysis
Mixed backpack is actually a comprehensive “01 backpack”, “complete backpack” and “multiple backpack” three traditional backpack problems.
We know that in one-dimensional space optimization, “01 knapsack” traverses the current capacity “from large to small”, while “complete knapsack” traverses the current capacity “from small to large”.
At the same time, “multiple knapsack” can be completely transferred to “01 knapsack” through “binary optimization”.
So we just need to choose a different traversal order depending on whether the first item is a “01 backpack” item or a “full backpack” item.
Code:
class Solution {
public int maxValue(int N, int C, int[] w, int[] v, int[] s) {
// Construct the "value" and "volume" lists of items
List<Integer> worth = new ArrayList<>();
List<Integer> volume = new ArrayList<>();
for (int i = 0; i < N; i++) {
int type = s[i];
// Multiple knapsack: Apply "binary optimization" to convert to 0-1 knapsack problem
if (type > 0) {
for (int k = 1; k <= type; k *= 2) {
type -= k;
worth.add(w[i] * k);
volume.add(v[i] * k);
}
if (type > 0) {
worth.add(w[i] * type);
volume.add(v[i] * type);
}
// 01 Knapsack: added directly
} else if (type == -1) {
worth.add(w[i]);
volume.add(v[i]);
// Complete backpack: mark worth by turning it over
} else{ worth.add(-w[i]); volume.add(v[i]); }}// Use the "one-dimensional space optimization" method to solve the three knapsack problems
int[] dp = new int[C + 1];
for (int i = 0; i < worth.size(); i++) {
int wor = worth.get(i);
int vol = volume.get(i);
// Full knapsack: the capacity is traversed "from small to large"
if (wor < 0) {
for (int j = vol; j <= C; j++) {
// Also remember to reverse worth to a positive integer
dp[j] = Math.max(dp[j], dp[j - vol] - wor);
}
// 01 knapsack: includes "original 01 knapsack" and "binary optimized full knapsack"
// The capacity is traversed "from large to small"
} else {
for (intj = C; j >= vol; j--) { dp[j] = Math.max(dp[j], dp[j - vol] + wor); }}}returndp[C]; }}Copy the codeThat’s how we solved the hybrid backpack problem.
Firstly, a “multiple knapsack” problem is transformed into a “01 knapsack” problem by the idea of “binary optimization”.
Then according to the item belongs to “01 backpack” or “complete backpack” to decide the capacity is “from large to small” or “from small to large” to calculate.
In other words, according to the type of item, choose different ways to transfer.
conclusion
Today we are going to look at the three traditional backpack problems before we look at the “hybrid backpack”.
The main difference between the three traditional knapsack is “the number of times items can be selected”, among which the one-dimensional optimization of “01 knapsack” is the basis of the rest of the knapsack problems.
For both the full pack and the multiple pack, one can select “any number of items” and the other has an “upper bound of selected items”.
This leads to the fact that both knapsack problems are essentially seeking the “maximum value of the entire prefix” and the “maximum value of the sliding window”, respectively, at some point in the transition.
This means that the “complete knapsack” can be reduced in time directly through one-dimensional spatial optimization; In the case of multiple knapsacks, the time complexity is reduced by “binary optimization” (reducing the total number of items) or “monotonous queue optimization” (achieving a sliding window maximum directly).
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
At the end of this section, we will have completed the first phase of the backpack problem 🎉 🎉
The following “knapsack problems” tend to be more “multi-dimensional”, “grouped”, “dependent”, and “solution number/specific solution”.
This kind of question is often really used to investigate the “backpack thinking” topic, the first stage of learning is more template questions, laying the foundation.
Keep it up