Multiple knapsack problem

This is a very old, very old, very early knowledge point. It is also one of the most classic DP (backpack) models.

Meaning: give the number of items n, the backpack volume V, and the volume V, value w, and quantity s of each item to find the maximum value sum.

Today, I have nothing to do, so I wrote multiple backpacks, three templates, corresponding to different algorithms.

Front cheese: 01 backpack, complete backpack learning, DP basic introduction

Multiple backpack 1 (\ (N \leq 100, V \leq 100\))

\(0 < v_i, w_i, s_i \leq 100\)

A simple knapsack. Just enumerate a few items directly.

The volume, value and quantity of articles are respectively expressed in V[i], W[i], C[i].

Let f[j] represent the maximum value that can be obtained when the volume of J is used. Taking items as the stage, we consider enumerating the number of items. Obviously, there is a transfer equation:

Where k represents the number of selected articles enumerated.

The time complexity is about \ (\mathrm{O(N^2V)} \)

Degenerate: when the number of items is all 1, it degenerates into a 01 backpack; When the number of items is far greater than the number of items that can be obtained by "take all the items", it is equivalent to a complete backpack.

About this question: the data is so small that you can disassemble all the items and convert them into 01 backpacks to do it. But obviously, this is not applicable to slightly larger data, such as when there are many items.

\(\mathrm{Code:}\) (the code style is slightly spooky)

#include <iostream>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i) 
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 101, M = 101;
int n, m, f[M], V[N], W[N], C[N], ans = 0;
inline int read() {
	int s = 0, _ = 1; char c = getchar();
	for (; !isdigit(c) && c != '-'; c = getchar());
	(c == '-' ? _ = -1, c = getchar() : 0);
	for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + c - 48;
	return s * _; 
}
template <typename T>
inline void write(T x) {
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	return putchar(x % 10 + 48), void();
}
signed main() {
	n = read(), m = read();
	FOR(i, 1, n) V[i] = read(), W[i] = read(), C[i] = read();
	FOR(i, 1, n) DOWN(j, m, V[i]) FOR(k, 1, C[i])
		if (j - k * V[i] >= 0) ans = std ::max(ans, f[j] = std ::max(f[j], f[j - k * V[i]] + k * W[i]));
	write(ans);
	return 0;
}

Multiple backpack 2 (\ (N \leq 1000, V \leq 2000\))

\(0 < v_i, w_i, s_i \leq 2000\)

In this data range, simple multiple knapsack is no longer applicable. We consider small Trick to optimize 01 knapsack.

What we need is to be able to select any number of items, while the limitation of 01 backpack is that we can only select a single item.

Then, inspired by the data of the previous stage, we set about optimizing the splitting.

Can I represent any integer in 0 ~ n? Binary split.

As we all know, binary is a very special base. For any integer x, it can be split:

b[i] is the i-th bit from right to left of the binary form of the integer, and the value is only 0 or 1. For other binary systems, we have to consider the problem of coefficients, but binary systems do not need them.

We dismantle the articles according to the whole power of 2 until the remaining quantity does not reach the whole power of 2, and then it becomes a separate article.

If the number of an item is 11, then it can be divided into \ (2^0,2^1,2^2,4\) these four items. You will find that any number from 0 to 11 can be pieced together by selecting or not selecting these three items.

The 01 backpack will help you "intelligently" choose which number is the best.

So just unpack the items and go directly to 01 backpack.

Greedy like: in the Acwing comment area of this topic, some DP with greedy selection optimization are proposed. Although there are counter examples, they are good in terms of efficiency, link.

PS: of course, combined with the complete backpack degradation mentioned earlier, this practice will be greatly improved, and even pass some OJ stage III templates.

\(\mathrm{Code:}\)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i)
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 1e6 + 10, M = 4e6 + 10;
int n, m, w[N], v[N];
struct Production { int s, w, v; } a[N];
inline int read() {
	int s = 0, _ = 1;
	char c = getchar();
	while ((c < '0' || c > '9') && c != '-') c = getchar();
	if (c == '-') c = getchar(), _ = -1;
	while (isdigit(c)) 
		s = (s << 1) + (s << 3) + c - 48, c = getchar();
	return s * _;
}
template <class T>
inline void write(T x) {
	if (x < 0) x = ~x + 1, putchar('-');
	if (x > 9) write(x / 10);
	return putchar(x % 10 + 48), void();
}
int f[M], len = 0;
void Spilt() {
	FOR(i, 1, n) {
		int t = 1;
		while (t <= a[i].s)
			w[++len] = t * a[i].w, v[len] = t * a[i].v, a[i].s -= t, t <<= 1;
		if (a[i].s) w[++len] = a[i].s * a[i].w, v[len] = a[i].s * a[i].v;
	}
}			// Binary split
signed main() {
	n = read(), m = read();
	FOR(i, 1, n) 
		a[i].w = read(), a[i].v = read(), a[i].s = read();
	Spilt();
	FOR(i, 1, len) DOWN(j, m, w[i])
		f[j] = std ::max(f[j], f[j - w[i]] + v[i]);
    		// Naked 01 Backpack
	write(f[m]);
	return 0;
}

Multiple backpack 3 (\ (N \leq 1000, V \leq 20000\))

\(0 < v_i, w_i, s_i \leq 20000\)

This data strengthens the volume and quantity of items, and the splitting method is no longer applicable. To achieve this amount of data, we need to improve it through DP optimization.

This topic is monotone queue optimization, pre cheese: monotone queue.

Observe our decisions for each transfer. That is, where we get the optimal value to update the current optimal value.

\(f\u j\) is transferred from \ (\{f_k| K \in J - h\times v\u i\}\), as shown in the figure:

We found that the yellow and orange values inherit from each other without interference, so we can classify them according to the remainder of \ (j \% V_i\) and calculate the answers respectively, because we found that a congruence class can be optimized.

So let's change the equation, and use u + p * V[i] to represent a certain j. that

The answer to the red dot is transferred from a yellow dot. Obviously, the yellow dot has some optimal values. Can we just maintain such optimal values in real time to avoid enumeration? The answer is yes.

We split the terms only related to i and only related to j in DP equation to obtain:

In the case of enumerating i and u, they can be regarded as constants. What we need to maintain is the value in max.

As we all know, monotone queues can eliminate the inferior items in time to maintain the monotone order of the set. Through this point, we maintain the monotonicity of the decision set (that is, the set of yellow decision points in the figure above).

Establish a monotonic queue q, which is empty at the beginning. Enumerate p again. Each operation:

• Exclude unavailable decisions first, that is, if the decision point is less than the lowest line \ (p - C_i\), you need to exclude the current decision.
• Update the current point with the optimal decision, that is, use q[h] to find \ (f\u{u + P \times v\u i}\), which can ensure that the decision is optimal through monotonic queue.
• Use the new decision point \ (f\u{u + P \times v\u i}\) to eliminate the poor decision of the team tail in time. The specific method is to compare the value of \ (f\u + K \times v\u i} - K \times v\u i\) and exclude the decision whose value is smaller than the current value.

\(\mathrm{Code:}\) (in order not to write the scrolling array, it has been changed to be very boring. For a more comfortable experience, please move Acwing a problem solution)

#include <iostream>
#define FOR(i, a, b) for (int i = (a), bb = (b); i <= bb; ++i)
#define DOWN(i, a, b) for (int i = (a), bb = (b); i >= bb; --i)
const int N = 1e3 + 10, M = 2e4 + 10;
int n, m, f[M], q[M], V[N], W[N], C[N];
inline int read() {
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c) && c != '-'; c = getchar());
    (c == '-' ? w = -1, c = getchar() : 0);
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + c - 48;
    return s * w;
}
template <typename T>
inline void write(T x) {
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    return putchar(x % 10 + 48), void();
}
inline int Calc(int i, int u, int x) { return f[u + x * V[i]] - x * W[i]; }
signed main() {
    n = read(), m = read();
    FOR(i, 1, n) V[i] = read(), W[i] = read(), C[i] = read();
    FOR(i, 1, n) FOR(u, 0, V[i] - 1) {
        int h = 1, t = 0, maxn = (m - u) / V[i];
        DOWN(k, maxn - 1, std ::max(maxn - C[i], 0)) {
            while (h <= t && Calc(i, u, q[t]) < Calc(i, u, k)) --t;
            q[++t] = k;
        }
        DOWN(p, maxn, 0) {
            while (h <= t && q[h] > p - 1) ++h;
            if (h <= t) f[u + p * V[i]] = std ::max(f[u + p * V[i]], Calc(i, u, q[h]) + p * W[i]);
            if (p - C[i] - 1 >= 0) {
                while (h <= t && Calc(i, u, q[t]) < Calc(i, u, p - C[i] - 1)) --t;
                q[++t] = p - C[i] - 1;
            }
        }
    }
    int ans = 0;
    FOR(i, 1, m) ans = std ::max(ans, f[i]);
    write(ans);
    return 0;
}