凑数(3)
创作者俱乐部成员
还是凑数问题:从A列的数里,找出求和等于B1的子组合。
🔔 | function* cs2(arr, s) { arr.sort((x,y)=>x-y) brr = arr.reduce((x,y)=>{ x.push(x[x.length - 1] - y) return x }, [s]) brr.reverse() arr.reverse() let len = arr.length let dat = [] yield* rec(0, 0, 0) function* rec(start, index, cur) { if (index === len) return for (let i = start; i < len; i++) { dat[index] = arr[i] let acc = cur + arr[i] if (acc === s) { yield dat.slice(0, index + 1) } else if (acc < s) { if (acc >= brr[i + 1]) { yield* rec(i + 1, index + 1, acc) } else { return } } } } } function coushu1(rng, s) { Application.Volatile(0) return JSON.stringify(cs2(rng().flat(), parseInt(s)).next().value) } function coushu(rng, s) { Application.Volatile(0) return [...cs2(rng().flat(), parseInt(s))].map(x=>[JSON.stringify(x)]) } |
改成了降序搜索,好像更快一点😁,这个版本算是能用,速度可以接受了
总的来说,对于凑数:
如果只有十几个数,用python的itertools循环遍历就很方便了
如果是几十个数,用这个函数找,速度还能接受
如果有数百上千个数,还是用规划求解找1个可行解吧,否则真的太慢了
明天再扩展一下小数,试试能不能发个在线文档吧