The bounded 0-1 multi-knapsack problem is a well-known problem in combinatorial optimization. It extends the classic knapsack problem by involving multiple knapsacks or bins, each with its own capacity. An item can have different profits, weights, and availability limits that define how many copies of an item can be used. This problem finds real-world applications in resource allocation, budget management, and cargo loading.

A pseudo-polynomial algorithm is often considered for solving the bounded 0-1 multi-knapsack problem, as the decision variables and constraints can be represented in a manner that leverages integer weights and profits. Here, we explore such an algorithm with technical explanations and examples.

Problem Definition

In the bounded 0-1 multi-knapsack problem, you are given:

• A set of n items, where each item i has a profit noted as p_i, a weight w_i, and an upper bound b_i indicating the maximum number of items available.
• m knapsacks, each with capacity C_j for the jth knapsack.

The goal is to select items to maximize the total profit without exceeding the capacity of any knapsack.

Pseudo-Polynomial Algorithm

The solution involves dynamic programming (DP), a technique that constructs solutions of a problem by building from solutions of smaller instances.

Dynamic Programming Approach

1. State Definition:
   Define a DP table dp[k][c], where dp[k][c] represents the maximum profit achievable with the first k items and a total capacity c.
2. Transition:
   To populate the table, iterate over each item i in the range from 1 to b[i] and for a total capacity from 0 to C_j. Update the cell with the rule dp[k][c] = max(dp[k-1][c], dp[k-1][c - count * w_k] + count * p_k).
   Here, count represents how many copies of item k you try to include, ranging from 0 to min(b_k, floor(c / w_k)).
3. Initialization:
   • Initialize dp[0][c] to zero, as no profit can be achieved with no items.
   • For capacity zero, dp[k][0] is zero since no profit can be gained without capacity.
4. Final Result:
   The maximum profit for knapsack j is found in dp[n][C_j].

Complexity

Given that the complexity of the algorithm relies on weights and capacities, it is pseudo-polynomial. The running time is O(n * C_j) for a single knapsack, making the entire approach O(m * n * C_j) for m knapsacks.

Example

Let's take a simple scenario with 2 items and 2 knapsacks:

• Items:
  • Item 1: p_1 = 60, w_1 = 10, b_1 = 2
  • Item 2: p_2 = 100, w_2 = 20, b_2 = 1
• Knapsack capacities:
  • C_1 = 50
  • C_2 = 40

The DP table would be 3-dimensional, accounting for knapsacks, items, and capacity. Here's an outline of the steps for knapsack 1:

• Consider item 1, for increasing capacity from 0 to 50, track profit:
  • Maximum of excluding the item or including up to b_1 of item 1 depending on whether capacity allows.
• Proceed similarly for item 2.

The final result for capacity C_1 of knapsack 1 could be at dp[2][50], and for knapsack 2 at dp[2][40].

Summary Table

Additional Considerations

In practice, for more efficiency, strategies such as using heuristic methods or approximations can be applied, especially when facing constraints with large values. However, these approximations may not guarantee an optimal solution as the pseudo-polynomial algorithm does for bounded inputs. Additionally, advancements in integer programming offer another layer for solving larger instances with specialized solvers.

Optimizing the bounded 0-1 multi-knapsack with this pseudo-polynomial algorithm showcases the blend between theoretical rigor and practical applicability, offering optimal results for a problem with significant computational challenges.