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 31, 2023

Patrick2788 

JosWoolley 's method of generating the combination matrix is fascinating for how efficient of a solution it is for a complex problem. From what I gather, it's based somewhat in binary (putting the 0 1 in 0 1 Knapsack!).

 

This produces the combination matrix before MMULT gets to it:

 

=MOD(INT(SEQUENCE(2^5,,0)/2^SEQUENCE(,5,0)),2)

 

 

I did some playing around with engineering functions.

 

Formula in K:

 

=BIN2DEC(I2)

 

Formula in N:

 

=DEC2BIN(K2,5)

 

 

 

 

 

 

 

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