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
Mar 30, 2023
I'm considering 5 at present. A previous discussion re:COMBINA ran into some limitations with setting upper bound too high.
JosWoolley's avatar
JosWoolley
Iron Contributor
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.

  • mtarler's avatar
    mtarler
    Silver Contributor
    Mar 30, 2023

    VERY nice. that delta variable that creates the full combination matrix is what we've been missing! I modified the file and formulas to do some testing and went out to 20 items!!! This version out performed the recursion by more than 2.5:1

     

    I also have to look at the recursion because I'm getting some errors and incorrect values from it ... (or maybe just throw it away since this solution is better in each way)

    btw here is the updated formula where I break the last line up to store the "mask" from delta and then can easily apply it to weights, and items

    =IF(D10,
LET(
    to,NOW(),
    α,benefit,
    β,weight,
    γ,COUNT(α),
    δ,MOD(INT(SEQUENCE(2^γ,,0)/2^SEQUENCE(,γ,0)),2),
    ε,MMULT(δ,TOCOL(α)),
    ζ,MMULT(δ,TOCOL(β)),
    η,ζ<=cap,
    benefitOut, MAX(FILTER(ε,η)),
    ansMask,INDEX(δ,MATCH(benefitOut,IF(η,ε),0),),
    itemOut,FILTER(item,ansMask),
    weightOut, SUM(FILTER(β, ansMask )),
    out,HSTACK((NOW()-to)*24*3600, "Benefit: " & benefitOut, "Weight: " & weightOut, "Items: " & TEXTJOIN(",",,itemOut )),
    out
    ),
"not run")

    I also have my poor-mans-timer and a 'toggle' to easily turn the calculation on/off

     

Resources