V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
burnbrid
V2EX  ›  算法

算法-在一组数中,把相加之和最近 100 的数,提取出来。

  •  
  •   burnbrid · 2019-08-20 09:14:06 +08:00 · 3999 次点击
    这是一个创建于 1922 天前的主题,其中的信息可能已经有所发展或是发生改变。

    算法-在一组数中,把相加之和最近 100 的数,提取出来。 举个例子:

    1 3 90 2 8 96 在这组数中应该把 96 和 3 这个俩个数提取出来。

    1 2 3 8 96 99 在这组数中应该把 99 这一个数提取出来。

    大神帮帮忙,我支持香港警察,你们可以帮我了。

    16 条回复    2019-08-20 10:28:16 +08:00
    maichael
        1
    maichael  
       2019-08-20 09:17:53 +08:00
    你这题有歧义呀,能提 1 个和 2 个,是不是还能提 3 个 4 个?限制条件不够。
    burnbrid
        2
    burnbrid  
    OP
       2019-08-20 09:21:48 +08:00
    @maichael 是可以提取多个数字,其实我的目的就是从一个池子里面抓钱,要尽可能的多抓钱。但是,抓的钱最多不能超过或等于 100 块。
    maichael
        3
    maichael  
       2019-08-20 09:24:14 +08:00
    @burnbrid #2 那你第一个例子里面,即可以选 90+8+1,也可以选 96+3,也可以选 96+3+1。答案也可以多个解吗?
    maichael
        4
    maichael  
       2019-08-20 09:24:34 +08:00
    @maichael #3 96+2+1
    misaka19000
        5
    misaka19000  
       2019-08-20 09:27:05 +08:00 via Android
    动态规划吧
    misaka19000
        6
    misaka19000  
       2019-08-20 09:27:52 +08:00 via Android
    动态规划
    burnbrid
        7
    burnbrid  
    OP
       2019-08-20 09:33:28 +08:00
    @maichael 是的,提取几个数字无所谓,最关键是不能超过 100 块。可以提取多个数字,也可以提取一个数字。其实我的目的就是从一个池子里面抓钱,要尽可能的多抓钱。但是,抓的钱最多不能超过或等于 100 块,至于你抓多少张钱我不关心,我关心的是抓的钱要尽可能接近 100 块但不能超过 100 块,。
    ytmsdy
        8
    ytmsdy  
       2019-08-20 09:36:07 +08:00
    f(x) = x_number +f(x -x_number)
    x_number:数组中第一个小于 x 的数字
    louiswang002
        9
    louiswang002  
       2019-08-20 09:38:20 +08:00 via iPhone
    动态规划-宝石谜题
    ahaxzh
        10
    ahaxzh  
       2019-08-20 09:44:18 +08:00
    dp
    ylsc633
        11
    ylsc633  
       2019-08-20 09:53:35 +08:00
    粗略一想 贪心算法

    又想了下,贪心算法不正常

    那就动态规划了
    finalwave
        12
    finalwave  
       2019-08-20 10:02:16 +08:00
    这不就是个容量 100 的背包问题,最多能塞多少
    kkeiko
        13
    kkeiko  
       2019-08-20 10:16:23 +08:00
    简单的思路:排序,头尾双指针,往中间走。复杂度 O(nlogn)
    进阶一点:动态规划,复杂度 O(n)
    wqzjk393
        14
    wqzjk393  
       2019-08-20 10:23:20 +08:00
    盲猜一个。。
    先 sort 一遍。
    定义一个余数变量初始为 100。遍历一遍数组,每遍历一个数令余数=(余数-当前数),然后在数组中小于余数的部分中再次遍历。每当余数-当前数小于 0 或者遍历完以后停止遍历,把余数和遍历到的数分别放进两个数组中。比较余数,然后找对应位置的遍历结果就是答案了。。
    kkk0406
        15
    kkk0406  
       2019-08-20 10:24:58 +08:00
    动态规划 背包问题
    antipro
        16
    antipro  
       2019-08-20 10:28:16 +08:00 via Android
    我想到一个简单办法,把这组数中所有可能的组合列出来各自求合,再做个倒序排序,最接近 100 的数字对应的组合就是你要的答案了,当然可能会有多个解。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   922 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 22:15 · PVG 06:15 · LAX 14:15 · JFK 17:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.