<jupyter_start><jupyter_text>The 0/1 Knapsack ProblemThis is an optimization problem.  We are given a collection, $T$, of $n$ items.  Item $i$ has weight $w_i$ and value $v_i$.  It's assumed that the weights and values are integers, and that these are all positive.  We have a _knapsack_ with a capacity $C$, i.e. it can hold a total weight $C$.  Our objective is to take the collection of items that together gives the maximum total value, without the total weight of the items exceeding the capacity $C$.  In mathematical terms, we want to find a subset $S \subseteq T$ that maximizes the total value.  In other words, we want to find $S$ such that$$\max_{S \subseteq T} \sum_{i \in S} v_i \ \mathrm{subject\ to} \ \sum_{i \in S} w_i \leq C.$$The "0/1" condition means that we are not allowed to take a fractional portion of any item, we have to either take an item or leave it behind.  (The Fractional Knapsack Problem allows us to take fractional portions of items.  That version has a greedy solution, which won't be discussed here.)  This "0/1" condition is what makes this problem "hard".  (Without going into any details of what this means, the 0/1 Knapsack Problem is an example of an [NP-complete problem](https://en.wikipedia.org/wiki/NP-completeness).  See also [here](https://www.mathsisfun.com/sets/np-complete.html), [here](https://www.geeksforgeeks.org/np-completeness-set-1/), or [here](https://www.ics.uci.edu/~eppstein/161/960312.html) for some introductions to this topic.)   A recursive solutionIn principle, an "easy" solution is that for each item we can consider two possibilities.  Either the optimal solution contains that item or it doesn't.  We consider both possibilities in a recursive manner and return the best solution found in this manner.<jupyter_code>import numpy as np
def knapsack(weight, value, capacity):
    if len(weight) != len(value):
        raise ValueError('weight and value lists must have same length!')
    if capacity < 0:
        return -np.inf
    if capacity == 0:
        return 0
    if len(weight) == 0:
        return 0
    
    #  Recurse on the two possible subproblems and return the best result.
    return max(knapsack(weight[:-1], value[:-1], capacity), 
               knapsack(weight[:-1], value[:-1], capacity-weight[-1]) + value[-1])<jupyter_output><empty_output><jupyter_text>A small example<jupyter_code>w = [1, 2, 3, 8, 7, 4]
v = [20, 5, 10, 40, 15, 25]
cap = 10

knapsack(w, v, cap)
cap = 11

knapsack(w, v, cap)<jupyter_output><empty_output><jupyter_text>Ok, but what items do I want?  While the previous method works to give us the maximum possible value of the items we can select, it doesn't provide us with an easy way to determine _what collection of items_ will give us that value.  It doesn't seem so straightforward to modify that recursive method to give the collection of items that gives the maximum value.  By writing a new method to determine the maximum value in a different fashion (by computing a table of values), we can trace back through the table to determine a collection of items that we want to take.  **Note:**  This isn't the most succinct code that I could have written, but I wanted to illustrate the method for filling in the table and finding the collection of items that give that maximum value.  Shorter code would consist of more list comprehensions, etc.<jupyter_code>from collections import namedtuple

item = namedtuple('item', ['w','v'])
def knapsack(weight, value, capacity, show_table=False, show_items=True):
    if len(weight) != len(value):
        raise ValueError('weight and value lists must have same length!')
    if capacity < 0:
        return -np.inf
    if capacity == 0:
        return 0
    if len(weight) == 0:
        return 0
    
    #  Each column is a maximum capacity value we can carry.
    #  Rows correspond to adding an additional item into consideration.
    #  Fill in the first row
    row = [value[0] if weight[0] <= k else 0 
           for k in range(capacity+1)]
    M = [row]
    
    #  Now fill in the rest of the rows
    for i, w, v in zip(range(1,len(weight[1:])+1), weight[1:], value[1:]):
        row = []
        for k in range(capacity+1):
            row.append(max(M[i-1][k], 
                      (M[i-1][k-w] + v if k-w >= 0 else 0)))
        M.append(row)
    
    current_capacity = cap
    items = []
    for r, w, v in zip(range(len(weight)-1, -1, -1), weight[::-1], value[::-1]):
        if (current_capacity-w >= 0) and \
            M[r][current_capacity] == (M[r-1][current_capacity-w] + v):
            items.append(item(w,v))
            current_capacity -= w
    
    if show_table:
        print(M)

    if show_items:
        return M[-1][-1],tuple(items)
    else:
        return M[-1][-1]
cap = 10

knapsack(w, v, cap)
cap = 11

knapsack(w, v, cap)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10327767470624613, 'fraction_numerical': 0.017316017316017316, 'mean_word_length': 3.226480836236934, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 15, 'https://': 4, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '453422', 'license': 'MIT', 'n_tokens_mistral': 1525, 'n_tokens_neox': 1448, 'n_words': 632, 'path': 'Knapsack-Problem.ipynb', 'repo_name': 'craw-daddy/dynamic_programming', 'size': '4851'}