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
Apr 08, 2023

A similar problem to the Knapsack is the Cutting Stock Problem:
https://en.wikipedia.org/wiki/Cutting_stock_problem

I see one of the methods for solving the problem is generating all possible combinations. The problem with using this method in Excel is the row limit/memory concerns. The Cutting Stock Problem seems to require the provided data be unstacked before combinations can be generated. However, generating all possible combinations for 200 items, pick 3 doesn't seem do-able. Other approaches involve first solving the problem as best as possible and then re-checking the values to make improvements where needed. Sounds like lots of recursion!

Resources