🌐 中文 English
This article aims to optimize the algorithmic logic for the Multiple Knapsack Problem. Test link for this chapter: https://www.luogu.com.cn/problem/P1776
What is the Multiple Knapsack Problem?
The Multiple Knapsack Problem is a problem that lies between the Complete Knapsack and the 0/1 Knapsack problems. Specifically, there are n types of items, but each type has a limited quantity. Due to this unique characteristic, the algorithmic logic and solution approach for the Multiple Knapsack Problem are closely related to the methods used for these two knapsack problems.
Basic Algorithmic Logic for Multiple Knapsack
When encountering the Multiple Knapsack Problem, it’s easy to think of the Complete Knapsack Problem and transform it into a variant of the Complete Knapsack. Test link (Here, we use the directly space-optimized Multiple Knapsack code. For the optimization logic article, please refer to my previous article):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<int> costs; // weight cost of each treasure
vector<int> vals; // value of each treasure
vector<int> nums; // total quantity of each treasure
vector<int> dp; // current knapsack capacity -> current value
int n, m; // total number of treasures, total knapsack capacity
// Strict position-dependent space optimization
int compute()
{
dp = vector<int>(m + 1, 0);
// Multiple Knapsack
for (int i = 1; i <= n; ++i)
{
for (int j = m; j >= 0; --j) // prevent overwriting previous values
{
// Purchase this treasure
for (int t = 1; t <= nums[i] && j - t * costs[i] >= 0; ++t)
{
dp[j] = max(dp[j], dp[j - t * costs[i]] + t * vals[i]);
}
}
}
return dp[m];
}
int main()
{
cin >> n >> m;
costs = vector<int>(n + 1);
vals = vector<int>(n + 1);
nums = vector<int>(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> vals[i] >> costs[i] >> nums[i];
}
cout << compute();
return 0;
}
The submission result is as follows:
As can be seen, the result is TLE (Time Limit Exceeded). This is because the time complexity of the Multiple Knapsack Problem is O(N * M * K), where N is the number of items, M is the knapsack capacity, and K is the quantity of items. This leads to excessively high time complexity, failing the test. Therefore, the algorithmic logic needs to be optimized.
Binary Grouping Algorithmic Logic for Multiple Knapsack
Algorithm Logic Example
As I mentioned earlier, the Multiple Knapsack Problem lies between the Complete Knapsack and the 0/1 Knapsack problems. When the time complexity of the Complete Knapsack solution is too high, we can transform the Multiple Knapsack Problem into a 0/1 Knapsack Problem and then solve it using the algorithmic logic of the 0/1 Knapsack. First, look at the code (the test link is the same as above. Note: Without space optimization, this problem may cause MLE (Memory Limit Exceeded), so a space-optimized version is required):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
vector<int> costs; // total weight cost in each group
vector<int> vals; // total value of all treasures in each group
vector<int> dp; // group idx + current knapsack capacity -> current value
int n, m; // total number of groups (invalid in 0/1 knapsack), total knapsack capacity
int len; // total number of items in the 0/1 knapsack
int compute1()
{
dp = vector<int>(m + 1, 0);
// 0/1 Knapsack
for (int i = 1; i <= len; ++i)
{
for (int j = m; j >= costs[i]; --j)
{
dp[j] = max(dp[j], dp[j - costs[i]] + vals[i]);
}
}
return dp[m];
}
int main()
{
cin >> n >> m;
// Add one redundant element
costs = vector<int>(1);
vals = vector<int>(1);
// Transform data into grouped knapsack
for (int i = 1, v, w, c; i <= n; ++i) // groups 1~n
{
cin >> v >> w >> c;
for (int j = 1; j <= c; j <<= 1) // start from selection, skip the entire group if not selected
{
costs.push_back(w * j); // cost of this group
vals.push_back(v * j); // value of this group
c -= j;
}
if (c > 0) // ensure no value exceeds the total, transform grouped knapsack into 0/1 knapsack
{
costs.push_back(w * c);
vals.push_back(v * c);
}
}
// After grouping, it can be treated as a 0/1 knapsack
len = vals.size();
cout << compute1();
return 0;
}
The result is as follows:
All tests passed!!!
Explanation of Binary Grouping Algorithmic Logic
In the Multiple Knapsack Problem, each type of item can be selected multiple times, but not exceeding the maximum quantity in a group. Therefore, the key to transforming it into a 0/1 Knapsack Problem is the “grouping” strategy. We continuously group by multiplying by 2 until grouping is no longer possible, then treat the remaining part as a separate group. This way, even if all items are selected, the total is still less than the maximum quantity, but any quantity can be achieved through different combinations. Finally, we solve the grouped problem using the algorithmic logic of the 0/1 Knapsack Problem. This reduces the time complexity to O(N * M * logK), where N is the number of items, M is the knapsack capacity, and K is the quantity of items. Compared to the previous O(N * M * K) time complexity, this is a significant optimization.
Monotonic Queue Algorithmic Logic for Multiple Knapsack
Using binary grouping still has an issue: if the quantity of items is too large, the number of groups after grouping will increase, leading to excessively high space complexity. Therefore, we need to further optimize the algorithmic logic. The monotonic queue algorithmic logic is an excellent optimization method that can reduce the time complexity to O(N * M), where N is the number of items and M is the knapsack capacity.
The test link is the same as above (using the space-optimized version). The code is as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
vector<int> costs; // cost
vector<int> nums; // quantity
vector<int> vals; // value
vector<int> dp; // one-dimensional dp
int l, r; // monotonic queue pointers
int n, t; // number of item types and knapsack capacity
int value1(int i, int j) {
return dp[j] - j / costs[i] * vals[i];
}
// Space optimization
int compute()
{
dp = vector<int>(t + 1, 0); // dynamic programming array
deque<int> q; // use deque to implement monotonic queue
for (int i = 1; i <= n; ++i)
{
for (int mod = 0; mod <= min(t, costs[i] - 1); ++mod) // minimum quantity or cost-1, add costs[i] group under different mods
{
q.clear();
for (int j = t - mod, cnt = 1; j >= 0 && cnt <= nums[i]; j -= costs[i], ++cnt) // take the correct position value
{
while (!q.empty() && value1(i, q.back()) <= value1(i, j))
{
q.pop_back();
}
q.push_back(j);
}
for (int j = t - mod, enter = j - costs[i] * nums[i]; j >= 0; j -= costs[i], enter -= costs[i])
{
if (enter >= 0)
{
while (!q.empty() && value1(i, q.back()) <= value1(i, enter))
{
q.pop_back();
}
q.push_back(enter);
}
dp[j] = value1(i, q.front()) + j / costs[i] * vals[i];
if (q.front() == j)
{
q.pop_front();
}
}
}
}
return dp[t];
}
int main()
{
cin >> n >> t;
vals = vector<int>(n + 1);
nums = vector<int>(n + 1);
costs = vector<int>(n + 1);
for (int i = 1; i <= n; i++) {
cin >> vals[i] >> costs[i] >> nums[i]; // input value, weight, and quantity
}
cout << compute();
return 0;
}
This solution requires grouping by congruence classes because adding integer multiples of the cost is possible under the same remainder. The value function is used to clarify the pattern, and under the same upper limit j, a monotonic queue is used for optimization.
Summary
The above are the three algorithmic logics for the Multiple Knapsack Problem. I hope this is helpful to you.
