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.

davidleal's avatar
davidleal
Iron Contributor
Mar 31, 2023

This is an interesting approach, but you have a limitation with binary numbers, the maximum number of digits is 10. Other than that it is great for generating the sequence and then splitting it:

 

=MID(DEC2BIN(SEQUENCE(2^5-1),5),SEQUENCE(,5),1)

 

 

Patrick2788's avatar
Patrick2788
Silver Contributor
Mar 31, 2023

davidleal 

I've seen some workarounds using concatenation to get around that 10 digit limit.

 

 

Here's my second take on Knapsack.

 

CombinMatrix
=LET(
    n, COUNT(item),
    combinations, SUM(COMBIN(n, SEQUENCE(n))),
    MAKEARRAY(combinations, n, LAMBDA(r, c, 1 * MID(DEC2BIN(r, 5), c, 1)))
)

Sheet level formula:
=LET(
    filtered, FILTER(CombinMatrix, MMULT(CombinMatrix, TOCOL(weight)) <= cap),
    b, MMULT(filtered, TOCOL(benefit)),
    stack, HSTACK(filtered, b),
    TAKE(DROP(SORT(stack, COUNT(item) + 1, -1), , -1), 1)
)

 

I've added an Include line:

 

Resources