LAMBDA函数递归：完全背包问题+10个元素全部子集

shaowu459

先来看第一个问题，完全背包问题。

有一个不含重复数值的正整数列表，要求从中选出和等于目标值的组合，列表中的数值可重复使用。
例如，已知数组是[7,3,2,5]，目标值是10，则共有以下5种组合：
7+3
3+3+2+2
2+2+2+2+2
3+2+5
5+5

这个题目和完全背包问题稍有不同，完全背包问题一般是指：有N件物品和一个能背重量为W的背包，第i件物品的重量为weight,价值为value。每件物品有无限个(也就是可以放入背包多次），求怎样可以使背包物品价值总量最大。

shaowu459

简单分析一下在Excel中使用LAMBDA函数递归的计算逻辑：
让原数组的每个数值都和原数组每个值相加（和值简称数组A），判断是否超过了目标值，如果超过了目标值就舍弃；如果等于目标值就提取出来当最终结果的一部分；如果小于目标值，则将数组A继续与原数组每个值相加，判断是否超过了目标值，如果超过了目标值就舍弃；如果等于目标值就提取出来当最终结果的一部分；如果小于目标值，则再次循环。


从上面的描述可以看出来，只要合计值没有超过目标值，就可以继续循环下去，模式一样，只不过初始值数组会变化，因此该问题可以用递归来解决。


假设递归公式定义为FX，则最终简化概况公式的最终目的是：=VSTACK(等于目标值的组合,FX(小于目标值的组合))，退出条件是超过目标值就退出。


根据上述分析，我们列出递归公式FX：

1. =LAMBDA(m,n,o,LET(c,TOROW(n),s,TEXTBEFORE(m,"="),t,TOCOL(s+c),u,t&"="&MAP(TOCOL(TEXTAFTER(m,"=")&"+"&c),LAMBDA(x,TEXTJOIN("+",,SORT(--TEXTSPLIT(x,,"+"))))),v,FILTER(u,t<o,0),VSTACK(UNIQUE(FILTER(u,t=o,0)),IF(@v=0,0,FX(UNIQUE(v),n,o)))))

复制代码

为了方便后续运算，我们给FX三个参数，FX(m,n,o)，m是加工后的初始数组（带=），n是初始数组，o是目标值。

定义好之后，假设数据存储在N2:N7单元格区域，则在任意单元格输入以下公式将获得各种方案：

1. =LET(s,N2:N7,t,FX(s&"="&s,s,50),FILTER(t,t>0))

复制代码

shaowu459

简单说明下公式各部分内容：
=LAMBDA(m,n,o,   设定3个参数

               LET(c,TOROW(n),   将原数组转成行
                     s,TEXTBEFORE(m,"="),  提取数组等号前的和值
                     t,TOCOL(s+c),   将此次运算前的和值+原数组每个值
                     u,t&"="&MAP(TOCOL(TEXTAFTER(m,"=")&"+"&c),
                                         LAMBDA(x,TEXTJOIN("+",,SORT(--TEXTSPLIT(x,,"+"))))),  将t和此次运算和的数组合在一起，因为要去重，所以给+链接的数组排排序
                     v,FILTER(u,t<o,0),   筛选出合计值小于目标值的数组
                     VSTACK(
                                  UNIQUE(FILTER(u,t=o,0)),   筛选出u里符合目标值的堆积，去重

                                  IF(@v=0,0,FX(UNIQUE(v),n,o))  小于目标值的数组v去重后进入下次循环
                                )
                     )
               )

shaowu459

第二个问题，输入10个元素全部不重复子集。举例来说，假设数组有1、2、3这3个元素，全部子集是：1、2、3这3个一个元素的，（1、2）、（1、3）、（2、3）这3个两个元素的，（1、2、3）这1个3个元素的。

公式比较简单，就不再单独说明了：

1. =LAMBDA(z,REDUCE(z,z,LAMBDA(x,y,IF(y=10,x,VSTACK(x,IF(y=9,{9,10},DROP(IFNA(HSTACK(HSTACK(0,y),fx(DROP(SEQUENCE(10),y))),HSTACK(0,y)),,1)))))))

复制代码

shaowu459

如果生成字符串，需要稍微调整，定义名称fx：

1. =LAMBDA(x,IF(ROWS(x)=1,x,VSTACK(@+x,@+x&fx(DROP(x,1)),fx(DROP(x,1)))))

复制代码

shaowu459

循环生成全部子集：

1. =REDUCE("",MID(A1,SEQUENCE(LEN(A1)),1),LAMBDA(x,y,VSTACK(x,x&y)))

复制代码

1. =REDUCE("",{1,2,3,4},LAMBDA(x,y,VSTACK(x,x&y)))

复制代码

锅仔335

用Excel试试欧拉计划吧，挺好玩的，至少能解100题

shaowu459

锅仔335 发表于 2023-3-18 01:51
用Excel试试欧拉计划吧，挺好玩的，至少能解100题

有挑选到有趣的题目可以分享哈

橒♂蝣

可以不用自定义名称了么？感觉很麻烦

shaowu459

橒♂蝣 发表于 2023-9-2 23:01
可以不用自定义名称了么？感觉很麻烦

目前，写递归公式必须得定义名称，没别的办法

更新：单元格递归直接可以写let(f,lambda(f,x,y这种方式。