<jupyter_start><jupyter_text>Setup Initialise PRNG.<jupyter_code>prng = np.random.RandomState(seed=42)<jupyter_output><empty_output><jupyter_text>Set number of items.<jupyter_code>n_items = 50<jupyter_output><empty_output><jupyter_text>Sample random values and weights.<jupyter_code>items = pd.DataFrame({
    'value': prng.randn(n_items),
    'weight': prng.randn(n_items)
})
items.head()<jupyter_output><empty_output><jupyter_text>Modelling Define the binary decision variables representing whether each item should be included in the solution.<jupyter_code>x = cvx.Variable(n_items, boolean=True)<jupyter_output><empty_output><jupyter_text>Define the total capacity.<jupyter_code>capacity = 100<jupyter_output><empty_output><jupyter_text>Define and solve the problem of maximising total value subject to the capacity constraint.<jupyter_code>problem = cvx.Problem(
    cvx.Maximize(x * items['value']),
    [x * items['weight'] <= capacity]
)
problem.solve()<jupyter_output><empty_output><jupyter_text>Check the solution.<jupyter_code>x.value.astype(int)<jupyter_output><empty_output><jupyter_text>Define a function to solve a random knapsack problem for `n_items` items and return the time it took.<jupyter_code>def time_random_knapsack_solution(n_items):
    values = prng.randn(n_items)
    weights = prng.randn(n_items)
    x = cvx.Variable(n_items, boolean=True)
    problem = cvx.Problem(cvx.Maximize(x * values), [x * weights <= capacity])
    start_time = time()
    problem.solve()
    return time() - start_time<jupyter_output><empty_output><jupyter_text>Run `time_random_knapsack_solution` for increasingly larger `n_items`.<jupyter_code>n_items = np.asarray([100, 1000, 10000, 100000])
times = np.asarray([time_random_knapsack_solution(x) for x in n_items])
times
times[1:] / times[:-1]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11960677225559803, 'fraction_numerical': 0.01474604041507373, 'mean_word_length': 7.52093023255814, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, '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': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '572279', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 683, 'n_tokens_neox': 643, 'n_words': 116, 'path': 'notebooks/02_ILP_Knapsack.ipynb', 'repo_name': 'gcampanella/pydata-london-2018', 'size': '1831'}