Problem description

There are n kinds of goods, which have their own volume, value and certain quantity. How to maximize the total value of the items loaded in the backpack with a given capacity?

Algorithmic thought

Before solving the problem, for the convenience of description, first define some variables: vi represents the value of the ith article, wi represents the volume or weight of the ith article, and si represents the quantity of the ith article. Definition V(i,j): current Backpack Capacity j, the value corresponding to the best combination of the first i items.

In fact, the multiple knapsack problem can be converted to 01 knapsack, so how to convert it? There is a simple idea: for the same item, if we regard different quantities of the item as a new variety, then this kind of item will become many new varieties, but each kind has only one, which will become a 01 backpack.

Let's suppose there are s items in the ith item. We can combine the same kinds of items. For example, i take out two pieces to merge into a new item, and i take out three pieces to merge into another new item. And so on, i take out s and merge them into a new item. Based on this idea, we can convert s items of item i into s items with different volume values, and then use the idea of 01 backpack to find the optimal solution!

The state transition equation can then be listed:

• j<w(i) V(i,j)=V(i-1,j)
• j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-s*w(i))+s*v(i)｝(s*w(i)<=j)

Explanation: for item I, we have capacity J. When the capacity J is less than w(i), this kind of goods can not be put down, so the maximum value of I kinds of goods in capacity J is equal to the maximum value of I-1 kinds of goods in capacity J, that is, V(i,j)=V(i-1,j); When the capacity J is greater than or equal to w(i), we can choose s pieces (not exceeding the capacity J) or not to take the ith item, so we should take a maximum value between the two.

So how? We only need to add a for loop when traversing the i-th item, traverse s items, and merge in the dynamic transfer equation! It should be noted that the volume of items we merged must not exceed the total volume of the current backpack (j), otherwise the merging is meaningless. The core code optimized with one-dimensional array is given below:

for (int i = 1; i <= n; i++)
{
    int w, v, s; //Volume, value, quantity
    cin >> w >> v >> s;
    for (int j = m; j >= w; j--)
    {
        for (int k = 1; k <= s && k * w <= j; k++)
            dp[j] = max(dp[j], dp[j - k * w] + k * v);
    }
}

Binary optimization

Simple thinking is very time-consuming, so it needs to be optimized. Binary optimization is a common optimization scheme.

In the simple solution, we need to divide each kind of goods into different categories according to the number 1~s, forming new types of volume and value. Although the pruning is optimized (k * w [i] < = J), the complexity is still high. The key to the problem is how to divide. Can we change an algorithm when dividing, no longer from 1 to s, and can also express 1 to s to produce the same effect! The answer must be yes. It is optimized with binary thought. Let's explain this idea below.

We know that any integer of 1~n can be expressed by binary thought. That is, a number can be decomposed into 1 + 2 + 4 + 8... + 2^n + remainder according to binary

For example, 7 can be written as 1 + 2 + 4, so numbers within 7 can be expressed by the sum of some of 1, 2 and 4.

Through the above principle, we can divide the s pieces of the i-th article into 1, 2, 4... To the rest according to the binary idea. Each quantity is regarded as a new variety. In this way, the complexity of the inner layer can be reduced from s to $\ log_{2}{s} $. The latter method is exactly the same as 01 backpack.

Code implementation:

sample input
4 5
1 2 3
2 4 1
3 4 3
4 5 2
sample output
10

#include <iostream>

using namespace std;

const int MAX = 100001;
int dp[MAX];
int w[MAX]; //volume
int v[MAX]; //value

int main()
{
    int n, m;    // n items, capacity m
    int cnt = 0; //For new category count
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int a, b, s; //Volume, value, quantity
        cin >> a >> b >> s;
        for (int j = 1; j <= s; j *= 2)
        {
            w[++cnt] = j * a;
            v[cnt] = j * b;
            s -= j;
        }
        if (s > 0) //If s there is surplus, it will become a new variety
        {
            w[++cnt] = s * a;
            v[cnt] = s * b;
        }
    }
    // 01 practice of backpacking
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = m; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    cout << dp[m];
    return 0;
}

Monotone queue optimization

Optimization thought

Let's first review the core code of simple thought:

for (int i = 1; i <= n; i++)
{
    int w, v, s; //Volume, value, quantity
    cin >> w >> v >> s;
    for (int j = m; j >= w; j--)
    {
        for (int k = 1; k <= s && k * w <= j; k++)
            dp[j] = max(dp[j], dp[j - k * w] + k * v);
    }
}

There is a triple for loop. i enumerates the number of items, j enumerates the backpack capacity, and k enumerates the number of each item. If we carefully observe the innermost cycle, we will find that the function of this cycle is to find a way to take the ith item of 0, 1, 2,..., s, so as to maximize the value when the capacity is j. His traversal process is from back to front, which is roughly as follows:

Note: the j-w,j-2w,... In the above figure does not refer to the value of the final method, but the previous state needs to be used. If I take t items of this kind, I need to reserve t*w space for this t item, and the remaining j-t*w space is the previous state we need to use.

Since the j of the middle layer loop is decreasing ergodic, when the next capacity is j-1, the whole ergodic process in the figure above can be expected to shift one grid to the left. By analogy, when j decreases to j-w, doesn't it coincide with the first one? Therefore, according to the volume (or weight) w of the ith article, we can divide the whole dp array into w equivalent classes, starting with 0,1,2,..., w-1. For the internal maximum of each equivalence class, we can use the monotonic queue decreasing from the head of the queue to the end of the queue, maintain the queue at all times, keep the head of the queue as the maximum, and the time complexity can be reduced to O(n*m).

The code is as follows:

sample input
4 5
1 2 3
2 4 1
3 4 3
4 5 2
sample output
10

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 100001;
int dp[MAX], g[MAX], q[MAX]; // g array is used to copy dp, and q array is used to form a monotonic queue to store the subscripts of the elements in g

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        memcpy(g, dp, sizeof(dp)); //Backup dp array
        int w, v, s;               //Volume, value, quantity
        cin >> w >> v >> s;
        for (int j = 0; j < w; j++)
        {
            int head = 0, tail = -1;
            for (int k = j; k <= m; k += w)
            {
                //Using the monotonic queue sliding window template, the window size is s*w, and the first element of the team is kept to the maximum
                while (head <= tail && k - s * w > q[head])
                    head++; //If the first element of the queue is not in the window, it will be kicked out of the queue
                if (head <= tail)
                    dp[k] = max(g[k], g[q[head]] + (k - q[head]) / w * v); //state transition 
                //If the end of the queue element is less than g[k], exit from the end of the queue
                while (head <= tail && g[k] >= g[q[tail]] + (k - q[tail]) / w * v)
                    tail--;
                // g[k] join the team
                q[++tail] = k;
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

Explanation of code details

g array is used to copy dp, and q array is used to form a monotonic queue to store the subscripts of the elements in g

(1)

while (head <= tail && k - s * w > q[head])
    head++;

q[head] refers to the subscript of the team head element, which is also the volume. For the current type of items, the maximum number is s and the volume is w, so the earliest state I want to use is k-s*w, so we should ensure that the first element of the team is within this range.

(2)

if (head <= tail)
    dp[k] = max(g[k], g[q[head]] + (k - q[head]) / w * v); 

This is the state transition equation. g array saves the data in the last state of dp array. Because dp will overwrite the previous data when it is constantly updated, g is used to save it. g[k] is the case of not taking it, and q[head] is the head of the monotonous queue, that is, the largest one. g[q[head]] is the state before the largest retrieval method is used, (k - q[head]) / w means several items are taken, and multiplied by v is the value of these items.

(3)

while (head <= tail && g[k] >= g[q[tail]] + (k - q[tail]) / w * v)
    tail--;
q[++tail] = k;

This is the maintenance of monotonic queues. G [k] should join the team from the end of the team, but I want to ensure that the whole queue is decreasing, that is, G [k] is the lowest after joining the team. So I use the while loop to start at the end of the team and remove all the items larger than g [k]. Then g[k] join the team.