Forum Discussion
Solving an 0 1 Knapsack Problem with LAMBDA
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 So I went with the recursive call option:
MaxPac = LAMBDA(items, benefits, weights, limit, [hide_text], LET(
i, IF(ROWS(items) = 1, TRANSPOSE(items), items),
b, IF(ROWS(benefits) = 1, TRANSPOSE(benefits), benefits),
w, IF(ROWS(weights) = 1, TRANSPOSE(weights), weights),
list, REDUCE(0, SEQUENCE(ROWS(i)), LAMBDA(q, p,
IF(INDEX(w, p) <= limit,
VSTACK(q, IF(ROWS(i) > p,
LET(sublist, MaxPac(DROP(i, p),DROP(b, p),DROP(w, p),limit - INDEX(w, p)),
IF( IFERROR(INDEX(sublist, 1), 0),
HSTACK(INDEX(b, p), INDEX(i, p)),
HSTACK(INDEX(b, p) + INDEX(sublist, 1, 1),
INDEX(i, p),
DROP(sublist, , 1))
)),
HSTACK(INDEX(b, p), INDEX(i, p))
)),
q))),
out, INDEX(SORT(list, 1, -1), 1, ),
hideText, IF(ISOMITTED(hide_text), FALSE, hide_text),
IF( hideText, out,
CONCAT("Benefit: ", INDEX(out, 1), " Items: ",
IFERROR(TEXTJOIN(",", 1, DROP(out, , 1)), 0)
)
)
))
It looks complicated but in concept it is easy. I check loop using REDUCE and check if that element is less than the weight limit, if so then I 'add' it to the list and re-call itself with the remainder of the elements. Each time I add a row and each row sums the Benefit in the first element. The last step is to sort by the Benefit and only Take/Return the highest value and pass that up the chain. There are a number of extra IFs and such because of making sure I don't strip off all the elements and such and in the beginning I check if the array is in a row or a column and swap it to make then columns if needed.
EDIT: I found some bug where the subcall must return an error or something in certain cases and I added an IFERROR() to the check. I also added some text/formatting that will be added only on the top call if that parameter is missing or set to false.
So I found this to be significantly faster in cases when all 5 objects are selected (i.e. the weights are all set below the total limit). I can only imagine that additional item list would also result in time improvements also.
On final note, this solution intentionally did not attempt to return all potential best solutions and just returns a best solution. In another words if there are more than 1 solution that returns the same maximum benefit, this solution will just return one of them.
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 - 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 ...
