Unveiling the Bounded Knapsack Problem

The Bounded Knapsack Problem is a classic dynamic programming problem.

The Bounded Knapsack Problem is a classic dynamic programming problem. The description of the problem is as follows:

There are n (n <= N) types of items and a knapsack with a capacity of m (m <= M). The i-th item has a quantity of s[i], weight of w[i], and value of v[i]. Now, we need to select some items to put into the knapsack, and the total capacity cannot exceed the capacity of the knapsack. Find the maximum total value of the items that can be achieved.

Bounded knapsack problem is a variation of 0/1 knapsack problem. In 0/1 knapsack problem, each item can only be chosen once, while in bounded knapsack problem, there are s[i] items of each type.

Compared with 0/1 knapsack problem, bounded knapsack problem is more difficult and has a variety of solutions.

The 0/1 knapsack problem is the core of the knapsack problem. If you are not familiar with it, you can refer to this article: 0/1 Knapsack Problem.

Straightforward solution

One very naive idea is to transform selecting each item s[i] times into having s[i] identical items, and then selecting each item once.

For example: items are:

           Weight   Value   Quantity

item 1      2        12        3

item 2      6        5         2

item 3      3        7         1

The above items can be converted into:

          Weight   Value   Quantity

item 1      2        12        1

item 1      2        12        1

item 1      2        12        1

item 2      6        5         1

item 2      6        5         1

item 3      3        7         1

This has become a 0/1 knapsack problem, and each item can only be used once.

Here is the C++ code:

#include <bits/stdc++.h>
using namespace std;


const int N = 1e3 + 7, M = 1e3 + 7;

int  f[N][M], w[N], v[N], s[N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; ++i) 
        cin >> w[i] >> v[i] >> s[i];   // Weight, value and quantity
    
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= s[i]; ++k)
                if(k * w[i] <= j)      // Choose each item k times
                    f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]); 
                    
    cout << f[n][m] << endl;   // Output result
    
    return 0;
}

Time complexity: O(N * M * s_max), considering the computation of the triple loop(s_max is the maximum value of the original item quantity).

Space complexity: O(N * M)

Disadvantages of the above solution

For example, suppose the quantity of the i-th item is 4, the impact on the capacity and value is the same for both of the following two cases:

• Select both the first and second items of item i

• Select both the third and fourth items of item i

Both are f[i - 1][j - 2 * w[i]] + 2 * v[i], so these two scenarios are completely equivalent.

Unfortunately, we have performed this repetitive work many times. Thus, optimizing the way items are split becomes a breakthrough in solving the problem.

Optimization for Bounded Knapsack Problem

Here we introduce a relatively common idea that can be used to optimize many problems, which is the binary lifting algorithm.

Let’s start with a simple example. Assuming there are a total of 11 items i.

Normally, to find the optimal solution, we need to enumerate 12 times (enumerate 0, 1, 2, … ,11 items).

Now, if we bundle these 11 items into the following four new items in advance:

• Containing 1 item

• Containing 2 items

• Containing 4 items

• Containing 4 = 11 — (1 + 2 + 4) items

We only need to enumerate 4 times to find the optimal solution. This greatly reduces the number of enumerations required.

This optimization is particularly significant for large numbers, such as when there are 1024 items. Under normal circumstances, we would need to enumerate 1025 times, but using this approach for the 0/1 knapsack problem, we only need to enumerate 10 times.

We can follow this idea: replace the original n items with ceil(log(n)) numbers to reduce the algorithm complexity.

More formal expression

The core idea is to continuously subtract 2^j(with j starting from 0) from the quantity s[i] of the i-th item. If 2^j exceeds the remaining items, the remaining items are packaged as the last large item.

I-th item has a quantity of s[i], which can be divided into two cases:

• If s[i] + 1 is a power of 2, bundle the s[i] items into j new items, each consisting of the following quantities of type i items:

• If s[i] + 1 is not a power of 2, then you need to add an item at the end that consists of a combination of the following quantities of type i items:

Here are some examples:

• 8 = 1 + 2 + 4 + 1

• 18 = 1 + 2 + 4 + 8 + 3

• 31 = 1 + 2 + 4 + 8 + 16

The italicized and bold numbers represent the last item added to reach the sum, while 31 doesn’t require any additions.

Clearly, by using the above splitting method, any number of items less than or equal to s[i] can be represented. After splitting each item in the above manner, the 0/1 knapsack method can be used to solve the problem.

In summary, the optimized code is as follows(One-dimensional spatialization has already been carried out):

#include <bits/stdc++.h>
using namespace std;


const int N = 11007, M = 2e3 + 7;

int  f[M], w[N], v[N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    // for(int i = 1; i <= n; ++i) 
    //     cin >> w[i] >> v[i] >> s[i];
    
    int cnt = 0;   // Number after packaging into a large item
    for(int i = 1; i <= n; i ++)
    {
        int weight, value, quantity;
        cin >> weight >> value >> quantity;
        
        int k = 1;  // Pack k small items into one large item
        while(k <= quantity)
        {
            cnt ++ ;    // Number of large items
            w[cnt] = weight * k;   // Weight of large items
            v[cnt] = value * k;    // Value of large items
            quantity -= k;
            k *= 2; 
        }
        
        // Pack the remaining items into one large item
        if(quantity > 0)
        {
            cnt++;
            w[cnt] = weight * quantity; 
            v[cnt] = value * quantity;
        }
    }

    n = cnt; 
    
    // One-dimensional transformation of 0/1 knapsack problem
    for(int i = 1; i <= n ; i++)
        for(int j = m ; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
                    
    cout << f[m] << endl;     // Output result
    
    return 0;
}

Time complexity: O(N * M * log(s_max)), s_max is the maximum value of the original item quantity.

Space complexity: O(N * log(s_max) + M), considering the space required for the loop of decomposing items and the space required for the loop of one-dimensional transformation.

Conclusion

This article explains the Bounded Knapsack Problem and its corresponding solution. By the idea of binary lifting, the original number of items with s[i] can be split into log(s[i]) pieces. This reduces the number of items when we convert to 0/1 knapsack problem by one order of magnitude.

However, this is not the optimal solution for the Bounded Knapsack Problem. In the future, the monotonic queue optimization method for the Bounded Knapsack Problem will be explained if there is a chance.

Finally, if there are any errors in the article, please kindly point them out. Thank you.