Is in Python "theme on", this paper details see active [link] (https://juejin.cn/post/6979532761954533390/)Copy the codereview
In the last lecture, we said that the multiple knapsack problem cannot be reduced by one-dimensional optimization in the same way as the full knapsack problem.
At the same time, items in multiple backpacks are “flattened”, which can be completely transformed into the 01 backpack problem.
However, as the number of items is not reduced, the enumeration will not be reduced, and the time complexity will not change, but increase the cost of flattening, making the constant of the algorithm larger.
In the case of the same order of magnitude in each dimension, the time complexity of the multiple knapsack we have learned can only solve problems of order of magnitude.
Topic describes
There are items and a backpack with a capacity of 5, and each item is “limited in quantity”.
The volume of the first item is, the value is, and the quantity is.
Ask which items to choose and how many items to choose for each item to maximize the total value.
In fact, based on the 0-1 knapsack problem, it added the feature that each item can be selected “a limited number of times” (as capacity allows).
Example 1:
Input: N = 2, C = 5, V = [1,2], W = [1,2], s = [2,1] Output: 4Copy the codeBinary optimization
Binary optimization can increase the number of multiple knapsack problems we can solve from an order of magnitude to.
Binary optimization refers to how we can completely transform a multiple knapsack problem into a 0-1 knapsack problem while reducing its complexity.
In the last section we flattened directly, an item of quantity is equivalent to.
This doesn’t reduce the amount of computation, but if we can get to less than, then this flattening makes sense.
If you have learned Linux, you know that the highest file permissions are 7, which means that you have read, write, and execute permissions. However, in fact, this 7 corresponds to 1, 2, and 4, namely r:1, W :2, and X :4. There are altogether 8 possible combinations of these three permissions.
Here we use the “compression” method of three numbers corresponding to eight cases.
We can also learn from this idea: replace n items with ceiL (log(n)) numbers to reduce algorithm complexity.
7 can be replaced with 1, 2, 4, like 10, we can replace it with 1, 2, 4, 3, and you might wonder, why 1, 2, 4, 3, instead of 1, 2, 4, 6 or 1, 2, 4, 8?
1, 2, 4, 6 can express the range of 0 13, while 1, 2, 4, 8 can express the range of 0 15, and we want to express the range of 10, greater than 10 can not be selected.
So we can add a number 3 (from 10-7) on the basis of 1, 2 and 4 (the range of expression is 0 and 7), which can satisfy the range of expression 0 and 10.
Take a look at the code that solves the multiple knapsack problem by flattening.
Java code:
class Solution {
public int maxValue(int N, int C, int[] s, int[] v, int[] w) {
/ / flat
List<Integer> worth = new ArrayList<>();
List<Integer> volume = new ArrayList<>();
// We want everything to be flat, so we walk through everything first
for (int i = 0; i < N; i++) {
// Get the number of occurrences per item
int val = s[i];
// Flatten: If an item is used 7 times, we flatten it into 3 items: 1* weight &1* value, 2* weight &2* value, and 4* weight &4* value
// Selecting the first flat item corresponds to using the item once. Selecting the second flat item corresponds to using the item twice. Selecting the first and second flat item corresponds to using the item 3 times.
for (int k = 1; k <= val; k *= 2) {
val -= k;
worth.add(w[i] * k);
volume.add(v[i] * k);
}
if (val > 0) { worth.add(w[i] * val); volume.add(v[i] * val); }}// 0-1 Knapsack problem solution
int[] dp = new int[C + 1];
for (int i = 0; i < worth.size(); i++) {
for (intj = C; j >= volume.get(i); j--) { dp[j] = Math.max(dp[j], dp[j - volume.get(i)] + worth.get(i)); }}returndp[C]; }}Copy the codePython 3 code:
class Solution:
def maxValue(self, N, C, s, v, w) :
# flat
worth = []
volume = []
# We wanted everything to be flat, so we walked through everything first
for i in range(N):
Get the number of occurrences per item
val = s[i]
# Flatten: If an item is required to be used 7 times, we flatten it into three items: 1* weight &1* value, 2* weight &2* Value, and 4* weight &4* Value
# Selecting all three items corresponds to using the item 0 times, selecting only the first flat item corresponds to using the item 1 times, selecting only the second flat item corresponds to using the item 2 times, selecting only the first and second flat item corresponds to using the item 3 times...
k = 1
while k <= val:
val -= k
worth.append(w[i] * k)
volume.append(v[i] * k)
k *= 2
if val > 0:
worth.append(w[i] * val)
volume.append(v[i] * val)
# 0-1 Knapsack problem solution
dp = [0] * (C + 1)
for i in range(len(worth)):
for j in range(C, volume[i] - 1, -1):
dp[j] = max(dp[j], dp[j-volume[i]] + worth[i])
return dp[C]
Copy the codeconclusion
Today we learned about binary optimization of “multiple knapsack”.
Unlike ordinary flattening, which “directly split the first item into pieces”, binary optimization can “split the original number of items into pieces”, making the number of items after we converted to 01 knapbag decreased by an order of magnitude.
The “binary optimized” multiple knapsack can solve data range from up to one second.
But this is not the upper limit of multi-knapsack problem optimization, and in the next lecture we will introduce better optimization than binary optimization.
The last
This is the No.* of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.