Superincreasing Sequences

Solving the Knapsack Problem Using a Superincreasing Sequence

Consider a set of numbers \(N = \{27, 2, 6, 13, 3\}\) with a knapsack capacity limit of 30. The objective is to fill the knapsack completely without exceeding this limit, using as many items from the set as possible, where each item's "volume" corresponds to the numbers provided: 27, 2, 6, 13, and 3. The challenge is to find a combination of these items that perfectly utilizes the knapsack's total volume of 30.

First, the elements of the set are arranged in ascending order to form a sequence:

$$a = \{2, 3, 6, 13, 27\}$$

This sequence is superincreasing, indicating that each element is greater than the sum of all previous elements, allowing the problem to be addressed using a polynomial algorithm. A linear combination of weights \(x_i\), where each can either be 0 or 1, is defined to achieve the target sum:

$$x_1 \cdot a_1 + x_2 \cdot a_2 + x_3 \cdot a_3 + x_4 \cdot a_4 + x_5 \cdot a_5 = m$$

Where \(a_1 = 2\), \(a_2 = 3\), \(a_3 = 6\), \(a_4 = 13\), \(a_5 = 27\), and the total to achieve is \(m = 30\).

$$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + x_5 \cdot 27 = 30 $$

The algorithm starts with the largest element and progressively considers each preceding item until the knapsack is either full or all items have been considered:

• Assigning the last weight: Compare the volume of the last item with the available space in the knapsack. If the space is sufficient, assign \(x_n=1\); otherwise, \(x_n=0\). $$x_n = \begin{cases} 1 \ \ \text{if} \ \ m \ge a_n \\ 0 \ \ \text{if} \ \ m < a_n \end{cases}$$
• Finding preceding weights: Using the same logic, compare the residual space with the volume of each subsequent item to decide whether it can be included. $$x_i = \begin{cases} 1 \ \ \text{if} \ \ m - \sum_{k=i+1}^n x_k \cdot a_k \ge a_i \\ 0 \ \ \text{if} \ \ m - \sum_{k=i+1}^n x_k \cdot a_k < a_i \end{cases}$$

Steps to solve:

1. I start with the largest item \( a_5 = 27 \) and assign \( x_5 = 1 \) if \(a_5 \leq m\); otherwise, \(x_5 = 0\). In this case, \(27 < 30\), so \(x_5 = 1\). This means the item can fit into the knapsack. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$
2. I update the remaining space value \( m = m - 27 = 3 \) considering the volume I've already inserted.
3. Proceed to the next item \(a_4 = 13\). Since \(13 > 3\), set \(x_4 = 0\) because the knapsack cannot also contain this item. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + \color{red}{0} \cdot 13 + 1 \cdot 27 = 30 $$
4. Next, consider \(a_3 = 6\), which cannot fit (\(6 > 3\)), so \(x_3 = 0\) because there is not enough space to insert it into the knapsack. $$ x_1 \cdot 2 + x_2 \cdot 3 + \color{red}{0} \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$
5. Then \(a_2 = 3\) matches the remaining space ( $ m = 3 $ ). Thus, I assign the weight \( x_2 = 1 \) because I can fit it into the knapsack. $$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$
6. I update the remaining space in the knapsack \( m = 30 - 27 \cdot 1 - 13 \cdot 0 - 6 \cdot 0 - 3 \cdot 1 = 0 \)
7. With no space left (\(m = 0\)), the algorithm concludes, leaving \(x_1 = 0\). $$  \color{red}{0} \cdot 2 +1  \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$

The optimal solution combines the volumes \(3\) and \(27\) to exactly fill the knapsack with \(30\):

$$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$

$$3 + 27 = 30$$

This approach is specific to superincreasing sequences and leverages their unique property to find a solution efficiently. It is not applicable if the sequence is not superincreasing.