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.

Thanks for your help

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

CodePudding user response：

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]))]

CodePudding user response：

This is a Knapsack problem. The problem is known to be NP-complete or harder, and there is no simple formula to solve the optimization problem you ask.

That is not to say that in the scenario you present there would not be a way to get a good enough result reasonably fast. See Knapsack_problem/Solving for possible approaches.