Knapsack

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Here is the mathematical formulation of the problem:

$$ \begin{eqnarray} \text{maximise} && \sum_{i=1}^{n} v_i x_i \\ \text{subject to} && \sum_{i=1}^{n} w_i x_i \leq W \end{eqnarray} $$

Where:

• $x_i$ is the quantity of element $i$,
• $v_i$ is the value of element $i$,
• $w_i$ is the weight of element $i$,
• $W$ is the maximum authorize weight.

Other constraints will define which variation of the algorithm to use.

</br>

Visualisation of the problem from Wikipedia

By extension, the algorithm used to resolve this problem is called the Knapsack algorithm.

Knapsack algorithm can also be used to similar problems such as the minimum number of coins needed to obtain a given value or also to determine if in a list of elements a sequence that sums to a given amount exists.

</br>

The idea of the algorithm is:

1) Define a list from 0 to the maximum weight and initialize all values to 0: the list values represent the maximum amount obtained for each weight. The first index represent a weight of 0 and its associated value is always 0 and the last index represent the maximum authorized weight

2) Iterate over each item and for each weight between the current item weight and the maximum weight, update the associated value as the maximum of the current associated value and the value of the current item + the value that we could obtain for the weight to update - the current item weight

3) Return the value obtained for the last element

</br>

Implementation

Knapsack with repetition: $w_i \in \mathbb{N}$

def knapsack(total, weights, values):
    # initialize a list with size equal the total weight to obtain
    dp = [0 for _ in range(total+1)]
    
    # iterate over the different weights
    for i in range(len(weights)):
        # check if the current weight can improve the obtained value for different total weight we can achieve
        for j in range(weights[i], total+1):
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
    print(dp)
    return(dp[-1])

knapsack(11, [6, 4, 8, 2], [30, 16, 14, 9])

[0, 0, 9, 9, 18, 18, 30, 30, 39, 39, 48, 48]

48

</br>

Knapsack without repetition: $w_i \in \{0,1\}$

Knapsack without repetition used two list to store weights value, 1 global and 1 temp. During the turn of a current item, as we can't use twice this item, a second 'temp' list is used to store the updates.

def knapsack_without_repetition(total, weights, values):
    # initialize a two list with size equal the total weight to obtain
    dp = [[0 for _ in range(total+1)] for _ in range(2)]
    
    # iterate over the different weights
    for i in range(len(weights)):
        # check if the current weight can improve the obtained value for different total weight we can achieve
        for j in range(weights[i], total+1):
            # using two different list protects from using twice the same weight
            dp[1][j] = max(dp[0][j], dp[0][j-weights[i]] + values[i]) # the value is stored in the second list but initiale values are taken from the first list
        # it is just at the end of this weight turn that we copy the second list in the first one
        dp[0] = [value for value in dp[1]]
    return(dp[1][-1])

</br>

Knapsack fractional amount without repetition: $w_i \in [0,1]$

Knapsack fractional can use fraction of element but can't take more than 1 time the element (otherwise just take as much as possible of the element with best value/weight ratio).

1) Compute for each element its value/weight ratio

2) Sort them from best to worse

3) Iterate over the item from best to worse

4) Take as much of this item as possible (with limit of 100% and that total weight is smaller than the authorized weight)

5) If there is still weight go to next element

def knapsack_fractional_without_repetition(total, weights, values):
    # Sort by ratios value/weight
    ratios = {i: values[i]/weights[i] for i in range(len(weights))}
    ratios = {k: v for k, v in sorted(ratios.items(), key=lambda item: -item[1])}
    
    # Take maximum amount of elements with best ratios
    total_value, remaining_space = 0, total
    for k, v in ratios.items():
        total_value += min(remaining_space, weights[k]) * v
        remaining_space -= min(remaining_space, weights[k])
        if remaining_space==0:
            return(total_value)
    return(total_value)

knapsack_fractional_without_repetition(10, [6, 4, 3, 2], [30, 16, 14, 9])