Forum Discussion
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...
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.
I nearly failed the test by forgetting to include a Lambda function!
Identifying the combinations was done through the application of binary numbers (not as Excel text though)
Combinationλ(n)
= LAMBDA(n,
LET(
k, SEQUENCE(1, 2 ^ n),
p, 2 ^ SEQUENCE(n, 1, 0),
SIGN(BITAND(k, p))
)
)
I've taken a look at BITAND a few times but didn't see a practical use for it so I didn't spend much time on it. The way it's used here makes sense in identifying where the bits line up and then using SIGN to get 1s and 0s. Both functions probably not originally designed with arrays in mind but capable of doing some lifting. It's good to have options!