清欢2020 2022-07-17 15:42 采纳率: 100%
浏览 166
已结题

从23个已知数中取n个数,n个数之和是250430,求是哪几个数之和

一共有23个已知数字,然后里面n个数之和是250430,n未知,现在需要知道是由哪几个数字组成了250430这个总数,只需要这个结果就行了,最好把代码也能给我,编程语言不限。证明不存在这个可能的话也可以。
23个已知数字:
20375
34665
26925
25060
22185
24375
22680
19195
19675
9800
10280
20090
22070
18765
18810
19180
15070
23000
18650
17320
21135
22440
18175

  • 写回答

5条回答 默认 最新

  • 请叫我问哥 Python领域新星创作者 2022-07-17 17:18
    关注

    先排序,然后深度优先。

    nums = [20375,34665,26925,25060,
    22185,24375,22680,19195,
    19675,9800,10280,20090,
    22070,18765,18810,19180,
    15070,23000,18650,17320,
    21135,22440,18175]
    
    tar = 250430
    
    def dfs(tar,nums,res):
        if sum(res)==tar:
            return res
        elif len(nums)<1 or sum(res)>tar:
            return False
        else:
            for i in range(len(nums)):
                temp = dfs(tar,nums[i+1:],res+[nums[i]])
                if temp: return temp
                elif temp==False: break
    
    nums = sorted(nums)
    print(dfs(tar,nums,list()))
    

    结果

    [9800, 10280, 15070, 17320, 18175, 18650, 18765, 19180, 20090, 20375, 21135, 26925, 34665]
    

    要找出所有的解,只要稍微改一下:

    def dfs(tar,nums,res):
        if sum(res)==tar:
            all_res.append(res)
        elif len(nums)<1 or sum(res)>tar:
            return False
        else:
            for i in range(len(nums)):
                temp = dfs(tar,nums[i+1:],res+[nums[i]])
                if temp==False: break
    
    nums = sorted(nums)
    all_res=[]
    dfs(tar,nums,list())
    print(len(all_res))
    print(sorted(all_res,key=len)[0])
    

    可以看到总共有323种解,n最少的解是

    323
    [15070, 18175, 18765, 20090, 22185, 22440, 22680, 24375, 25060, 26925, 34665]
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(4条)

报告相同问题?

问题事件

  • 系统已结题 7月25日
  • 已采纳回答 7月17日
  • 修改了问题 7月17日
  • 创建了问题 7月17日

悬赏问题

  • ¥15 微信夜间被转走了1w对,当天手机剪切板里就出现了这个乱码,有铁子可以看看是啥吗可以
  • ¥50 跑通github上的代码 深度学习 pytorch
  • ¥50 求写,批处理调用分区助手分区脚本
  • ¥15 求购HI3519AV100开发板
  • ¥15 请问1553 RT怎么测试,没有BC有方法吗
  • ¥100 业务编程如何选择学习方向和内容?
  • ¥15 wamp3.3.5安装完成后图标正常显示绿色,鼠标左右键点击图标均无反应。求解决方法。
  • ¥15 鼠标点击的这条记录了什么?
  • ¥15 在写pid调速的程序时,电机始终维持最大速度
  • ¥15 【有偿】调用DXGI截图初始化失败,提示0xf 887a0004