Introduction

The Multiple-Choice Knapsack Problem (MCKP) is a variation of the classic Knapsack Problem where items are grouped into classes, and from each class, only one item can be selected to be part of the solution. This problem can be found in various real-world scenarios, including resource allocation, project selection, and decision-making processes in business logistics. In this article, we will delve into the Python implementation of the MCKP, discussing the algorithmic approach, and providing code examples and explanations.

Problem Definition

In the MCKP, we are given several classes of items, each with different weights and values. The goal is to choose exactly one item from each class such that the total weight does not exceed the given knapsack capacity, and the total value is maximized.

Mathematical Formulation

Let there be n classes, and each class i contains m_i items. Each item j in class i has a weight w_\{i,j\} and a value v_\{i,j\} . The problem can be formulated as:

Maximize:
$Z = \sum_{i=1}^{n} \sum_{j=1}^{m_i} v_{i,j} \cdot x_{i,j}$

Subject to:
$\sum_{i=1}^{n} \sum_{j=1}^{m_i} w_{i,j} \cdot x_{i,j} \leq C$
$\sum_{j=1}^{m_i} x_{i,j} = 1 \, \forall i \in {1, 2, \ldots, n}$
$x_{i,j} \in {0, 1} \, \forall i, j$

Where: • Z is the total value. • C is the maximum capacity of the knapsack. • x_\{i,j\} is a binary variable representing whether item j from class i is chosen.

Dynamic Programming Approach

The MCKP can be efficiently solved using dynamic programming (DP). The underlying idea is to build a DP table with dimensions equal to the number of classes and knapsack capacity. Each cell of the DP table represents the maximum value attainable with a certain number of classes and a specific knapsack capacity.

Dynamic Programming Table

Let dp[i][c] represent the maximum value that can be achieved using the first i classes with a capacity c .

State Transition

The state transition can be defined as:

For each item j in class i :
If w_\{i,j\} <= c :
$dp[i][c] = \max(dp[i][c], dp[i-1][c - w_{i,j}] + v_{i,j})$

The solution is found in dp[n][C] , which provides the maximum value achievable using all n classes and total capacity C .

Python Implementation

Here's a Python implementation of the MCKP using dynamic programming:

• Data Structure: A list dp of size (capacity + 1) is maintained to store the maximum values for each possible capacity. • Outer Loop: Iterates over each class. • Inner Loop: Traverses each item in the class and updates the DP table from right to left to ensure each item is only considered once per class.