Knapsack problem: choose 5 elements among 100, weight <= 100, maximise total value

I have a data table containing n=100 elements :

And I would like to create an algorithm to get 5 elements where :

• sum of the 5 weights is capped to 100
• sum of the 5 values should be the maximum possible

I'm on google sheet but I don't know how to do it properly.

I tried to iterate on every element but it was not really effective...

I'm not familiar enough with google sheets, but here is a simple recursive function with memoization in python, using the following recurrence formula:

if weight(n) <= w:
    T(n, k, w) = max(
                     T(n-1, k, w),
                     value(n) + T(n-1, k-1, w-weight(n))
                 )
else:
    T(n, k, w) = T(n-1, k, w)

where

• T(n, k, w) is the maximum sum of k values whose weights sum up to at most w, using only items up to the nth item
• T(100, 5, 100) is the overall solution to your problem
• if the best solution for (n, k, w) doesn't use the nth item, then it's equal to the best solution for (n-1, k, w)
• if the best solution for (n, k, w) uses the nth item, then it's equal to the the value of the nth item plus the value of the best solution for (n-1, k-1, w-weight(n))

In python:

import numpy as np

n_items_total, k_items_solution, max_weight = 100, 5, 100

data = np.random.randint(0, max_weight+1, (n_items_total,2)))

def knapsack(n, k, w):
    if (n, k, w) not in knapsack.t:
        if w < 0 or n < 0 or k < 0:
            knapsack.t[(n, k, w)] = -1000  # big negative number, large enough that solution is invalid
        elif n < k:
            knapsack.t[(n, k, w)] = -1000 # presuming you want exactly k items; remove this line if <= k is okay
        elif k == 0:
            knapsack.t[(n, k, w)] = 0
        else:
            knapsack.t[(n, k, w)] = max(knapsack(n-1, k, w), data[n-1, 0] + knapsack(n-1, k-1, w-data[n-1,1]))
    return knapsack.t[(n, k, w)]
knapsack.t = {}

def traceback_solution(t, n, k, w):
    if k <= 0:
        return
    s = t[(n, k, w)]
    a = t[(n-1, k, w)]
    b = data[n-1, 0] + t[(n-1, k-1, w-data[n-1, 1])]
    if s == a:
        yield from traceback_solution(t, n-1, k, w)
    elif s == b:
        yield (n-1, data[n-1])
        yield from traceback_solution(t, n-1, k-1, w-data[n-1, 1])
    else:
        raise Error

best_score = knapsack(n_items_total, k_items_solution, max_weight)
solution = list(traceback_solution(knapsack.t, n_items_total, k_items_solution, max_weight))

print(solution)
# [(87, array([97,  2])),
#  (84, array([97, 29])), 
#  (63, array([98, 11])), 
#  (36, array([98, 32])), 
#  (0, array([99,  6]))]