凑数(3)

wils
wils

创作者俱乐部成员

还是凑数问题:从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个可行解吧,否则真的太慢了

明天再扩展一下小数,试试能不能发个在线文档吧

海南省
浏览 304
收藏
2
分享
2 +1
+1
全部评论