数学吧 关注:895,001贴子:8,764,209
  • 6回复贴,共1

求教数学大佬,下面的这种问题怎么设计算法效率最高

只看楼主收藏回复

就是从给定数组中挑出若干个数,让这若干个数的数的和等于某数,
如果找到,则返回这些数
如果找不到,返回false
例如
输入数组: [3.58, 7, 8, 10, 68.93, 80, 84.28, 90.21, 94.1, 100, 126.37, 126.83, 217.75, 281, 322.38, 384.91, 385, 448.17, 586.72, 623.8, 876, 920.14]
输入需要等于的和: 3684.77
输出结果:[68.93, 80, 84.28, 90.21, 100, 126.37, 217.75, 281, 322.38, 384.91, 385, 623.8, 920.14]
输入数组是已知的,输入数组的长度不大于30
和( 3684.77 )也是已知的
从数组中取数的个数和具体取哪些数,事前是不知道的,要通过算法算出来


IP属地:甘肃1楼2024-10-17 23:38回复
    穷举吧
    先按降序排个序,然后dp。
    dp(list<int> choice, int i)
    if sum(choice)==target
    then return choice
    end if
    if sum(choice)<target
    dp(choice+[nums[i]], i+1)
    dp(choice, i+1)
    end if
    差不多就是这个样子。这样要求全是正数。如果有正有负,还能改改


    IP属地:上海来自Android客户端2楼2024-10-17 23:57
    收起回复
      自顶一下


      IP属地:甘肃来自Android客户端3楼2024-10-18 08:28
      回复