This is the 22nd day of my participation in Gwen Challenge
preface
Today is the eleventh in our series on dynamic programming called the Knapsack problem.
Today we’re going to look at the “mixed backpack” problem, and this is the last part of the first part of our “backpack problem.”
I’m going to start today with a review of the three backpack problems we’ve seen before.
Then through a “mixed backpack” problem, we will learn several backpack problems in series.
Hopefully this will give you a clearer idea of the backpack problem.
In addition, AT the end of the article, I listed the related topics about the backpack problem that I sorted out.
I will explain the backpack problem in the order it is arranged (update every few days to make sure you digest it).
You can also try to do it first, you are also welcome to leave a message to me, you feel related to backpack DP type topic ~
Review three traditional backpack problems
So we’ve done three traditional backpack problems.
Here are three more traditional backpacks:
-
01 Backpack: Emphasize that each item ** can only be selected once. Time complexity cannot be reduced by “one-dimensional space optimization”, which requires “traversal of the capacity dimension from large to small” **.
-
Full backpack: Emphasizes that each item ** can be selected an unlimited number of times. The “one-dimensional space optimization” has mathematical significance, which can reduce the time complexity from to, and the “one-dimensional space optimization” requires “traversal of the capacity dimension from small to large” **.
-
Multiple packs: Emphasize that each item ** can only be selected a limited number of times **. Neither “one-dimensional space optimization” nor “ordinary flattening” can reduce the time complexity, and additional optimization means should be applied: binary optimization or monotone queue optimization.
The “difficulty” of the three knapsack problems is “increasing”, but the “importance” is “decreasing”.
Although “multiple knapsack” binary optimization and monotonic queue optimization are more trick.
But “multiple backpacks” isn’t so common that I couldn’t find a title for “multiple backpacks” in LeetCode.
Meanwhile, the three knapsack problems have two state definitions: ** “no more than” and “just”.
These two state definitions differ only in “initialization.”
How to initialize is to grasp what state is legal:
-
For definitions of “not exceeding” states: all are valid values.
Represents not considering any items, backpack capacity “does not exceed” the maximum value obtained.
-
For the state definition of “exactly” : only valid values are in, and all other values are “invalid values”.
Is not considering any items, only the backpack capacity “just” when the maximum value is obtained; Any other capacity that “happens to be not” cannot achieve effective value (because no item is considered).
In general, the three knapsack problems are so classical (combinatorial optimization problems in nature) that the knapsack problem directly becomes a kind of dynamic programming model.
My advice is to master all three. But if it comes down to prioritising, I’d rather you spend most of your time on the 01 pack versus the Full Pack.
Mixed backpack
Given the number of items and backpack capacity. The volume of the first article is, the value is, and the available quantity is:
-
This item can only be used once
-
When represents the item can be used an unlimited number of times
-
Any positive integer indicates the number of available times
Figure out which items to put into the backpack so that the total cost of these items does not exceed the backpack capacity and the total value is maximum.
Fundamental analysis
Mixed backpack is actually integrated “01 backpack”, “complete backpack” and “multiple backpack” three traditional backpack problems.
We know that in the one-dimensional space optimization mode, “01 backpack” traverses the current capacity according to “from large to small”, while “full backpack” traverses the current capacity according to “from small to large”.
Meanwhile, “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, List<Integer> worth = new ArrayList<>(); int[] s) {List<Integer> worth = new ArrayList<>(); List<Integer> volume = new ArrayList<>(); for (int i = 0; i < N; i++) { int type = s[i]; 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); } else if (type == -1) {word.add (w[I]); volume.add(v[i]); } else {worth.add(-w[I]); volume.add(v[i]); Int [] dp = new int[C + 1]; for (int i = 0; i < worth.size(); i++) { int wor = worth.get(i); int vol = volume.get(i); If (wor < 0) {for (int j = vol; j <= C; Dp [j] = Math. Max (dp[j], dp[j-vol] -wor); } else {for (int j = C;} else {for (int j = C; j >= vol; j--) { dp[j] = Math.max(dp[j], dp[j - vol] + wor); } } } return dp[C]; }}Copy the codeThat’s how we solved the hybrid backpack problem.
First, a “multiple knapsack” problem through the “binary optimization” idea, into the “01 knapsack” problem.
Then, according to whether the item belongs to “01 backpack” or “full backpack,” determine whether the capacity is “from large to small” or “from small to large.”
In other words, according to the different types of items, choose different transfer methods.
conclusion
Today we are going to look at the three traditional backpack problems before we learn about “hybrid backpack”.
The main difference between the three traditional backpacks is “the number of times items can be selected”, among which the one-dimensional optimization of “01 backpacks” is the basis of the rest of the backpack problem.
For “full backpack” and “multiple backpack”, one can choose “any number of items”, and the other has “upper bound of items”.
As a result, the essence of these two knapsack problems is to find “the maximum value of the whole prefix” and “the maximum value of the sliding window” when they are transferred to a certain point.
This means that “full knapsack” can directly reduce the time complexity through one-dimensional optimization; Multiknapsack reduces time complexity through “binary optimization” (reducing the total number of items) or “monochromatic queue optimization” (allowing direct optimization of sliding window maxima).
The last
By the end of this section, we will have completed the first stage of the “backpack problem” π π
The following “knapsack problem” tends to be more “multidimensional”, “grouping”, “dependent” and “finding the number of solutions/specific solutions”.
This kind of question is often really used to investigate the “backpack thinking” of the topic, the first stage of learning is more template questions, with the foundation.
Keep it up
In addition, the recent period of time of the update frequency of the public did decline
Many students through various channels (LeetCode comment area, Zhihu, public number background) urge more…
But I really did not lazy π€£
Here’s what you’ve been up to:
-
I must be busy with my work first
-
The next is a PDF that is being organized into a reasonable layout and order, which will be available for download later
-
The last one is the Easter egg announcement: recently, we are planning to cooperate with LeetCode to publish two Leetbooks π π. At that time, we will still provide them to everyone π€£ in the form of “free & non-member”, so that everyone can have a better learning experience ~
Stay tuned
After a while, the official account will return to the “3~4 weekly” update frequency drip ~
Backpack Problem (Table of Contents)
Due to the “backpack problem”, there are no template questions in LeetCode for many template questions, and the public account cannot put external links, so we built a backpack warehouse tonight.
We will give each article a corresponding original address. Welcome Mark ~
Full address: github.com/SharingSour…
-
Knapsack: Knapsack problem first lecture
-
01 Backpack: Backpack problem In Lecture 2
-
01 Backpack: Backpack problem Lecture 3
-
Complete knapsack: Lecture 4 of the knapsack problem
-
Complete backpack: The backpack problem lecture 5
-
The whole backpack problem Lecture 6
-
Complete knapsack: Knapsack problem Lecture 7
-
Multiple backpacks: Lecture 8 on the Backpack Problem
-
Multiple backpacks
-
γ I γ Multiple Knapsacks: The Knapsack Problem lecture 9
-
Multiple Knapsack (Optimization) : Knapsack problem lecture 10
-
Hybrid backpack: This article
-
Mix the backpack
-
Packet backpack
-
γ exercise γ Pack in groups
-
Multidimensional knapsack
-
Multidimensional backpack
-
The tree backpack
-
A tree backpack
-
Knapsack solution number
-
γ ε Έ ε θ δΎ 2 γ The number of options is the same as the number of options
-
Backpack for specific programs
-
γ practice γ backpack to find a specific plan
-
Generalization backpack
-
γ exercise γ Generalization backpack
- []