Forum Discussion

Patrick2788's avatar
Patrick2788
Silver Contributor
Mar 29, 2023
Solved

Solving an 0 1 Knapsack Problem with LAMBDA

A Knapsack Problem is defined as: Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given l...
excel
Formulas and Functions
office 365
  • JosWoolley's avatar
    JosWoolley
    Mar 30, 2023

    Patrick2788 

     

    I think I'd prefer to avoid any recursion or LAMBDAs and resort to some good old-fashioned matrix multiplication!

     

    =LET(
    α,benefit,
    β,weight,
    γ,COUNT(α),
    δ,MOD(INT(SEQUENCE(2^γ,,0)/2^SEQUENCE(,γ,0)),2),
    ε,MMULT(δ,TOCOL(α)),
    ζ,MMULT(δ,TOCOL(β)),
    η,ζ<=cap,
    TEXTJOIN(",",,
        FILTER(item,INDEX(δ,MATCH(MAX(FILTER(ε,η)),IF(η,ε),0)),0)
    )
)

     

    No doubt this could be refined, though the basic outline is there.

Patrick2788's avatar
Patrick2788
Silver Contributor
May 20, 2025

Another approach for 2025 using a random bin array.  This is in part inspired simulated annealing (Although, there's no cooling being done here) and maybe Monte Carlo methods but might be closer to brute force:

Knapsackλ = LAMBDA(items, values, weights, limit, trials,
        LET(
        //Generate random, unique BIN array
            bin, UNIQUE(RANDARRAY(trials, COUNT(items), 0, 1, 1)),
        //Determine which rows are within limit
            retain, BYROW(IF(bin, weights, 0), SUM) <= @limit,
        //Get the rows of values within limits
            keep, FILTER(IF(bin, values, 0), retain),
        //Sort the kept rows and sign
            return, SIGN(TAKE(SORTBY(keep, BYROW(keep, SUM), -1), 1)),
            return
        )
    );

I've added a few more items:

So far the results are fairly accurate.  I added an item with benefit and weight of 1 because for most all scenarios this item should be included.

Resources