Forum Discussion

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...

Solving an 0 1 Knapsack Problem with LAMBDA.xlsx178 KB

excel

Formulas and Functions

office 365

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

Silver Contributor

Mar 30, 2023

mtarler

Your solution seems to be the equivalent to the VBA solutions I found in research where 5 levels of nested loops were being used. To your credit, I think your solution is a lot more accurate. I played around with stepping through vba solutions line-by-line because I was wondering about the order the checks were being done in. I bagged the vba stuff when a few of the solutions returned 0 for an answer!

Writing recursive functions is tricky to me because one has to write with a sense of anticipation in mind. If I understand your solution, initiallly the checks on number of rows with Items, Weights, and Benefits is done because the array must be checked after the function has been run to see if the TRANSPOSE is needed. It's obvious the number of rows is 1 on the first pass but not on subsequent runs.

Timings

4-digits

0.3086568

0.3444158

0.3086526

0.3095298

0.3091404

mtarler

Silver Contributor

Mar 30, 2023

So I do that rows check because my brain and such was working that way when I wrote the first draft of the function and it failed because it only saw 1 row on the input so instead of trying to re-think it all I just converted horizontal data to vertical data.
The nice thing about the recursion is that it will work for as many levels as Excel can handle (i.e. it doesn't have 5 fixed loops). The nice thing about my solution only looking for ONE max result (and not all solutions possible for the max result) is that it will go 'down' and 'up' the recursion ladder and keep returning 1 value after each tier. Actually thinking now, technically for that matter, even if I returned 'all' options it would still be 1 2-d array because of the REDUCE, but then I would have to 'add' the next up tier to every returned row ...