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

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

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

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

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

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

    可以提取多个数字,也可以提取一个数字。其实我的目的就是从一个池子里面抓钱,要尽可能的多抓钱。但是,抓的钱最多不能超过或等于 100 块。

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

    11 条回复    2019-08-20 14:52:53 +08:00
    smilzman
        1
    smilzman  
       2019-08-20 09:35:34 +08:00   ❤️ 1
    关键词:背包问题、贪心算法
    arrow8899
        2
    arrow8899  
       2019-08-20 09:38:35 +08:00
    楼上说得对,不过如果你数据量很小的话,暴力破解也行
    mangoDB
        3
    mangoDB  
       2019-08-20 09:40:15 +08:00
    为什么要发两个帖子?
    burnbrid
        4
    burnbrid  
    OP
       2019-08-20 09:41:47 +08:00
    @mangoDB 着急解决,感觉算法板块的人没程序员版本的人多,所以在程序员板块下又发了一次。
    burnbrid
        5
    burnbrid  
    OP
       2019-08-20 09:42:06 +08:00
    @smilzman 谢谢,我 Google 一下。
    deleteDB
        6
    deleteDB  
       2019-08-20 09:52:17 +08:00
    @mangoDB 名字好像啊 还以为是我自己回复的
    todd7zhang
        7
    todd7zhang  
       2019-08-20 09:55:21 +08:00
    也可以是 ksum 的问题, 先排序, 再递归到 2Sum, 复杂度 O(n^(k-1)logn)
    taogen
        8
    taogen  
       2019-08-20 11:03:47 +08:00 via Android
    动态规划可以解决,类似 0/1 背包问题。
    noqwerty
        9
    noqwerty  
       2019-08-20 11:24:35 +08:00 via Android
    背包问题,以前帮老婆对账的时候写过......
    https://leetcode.com/problems/coin-change-2/
    jzmws
        10
    jzmws  
       2019-08-20 13:27:39 +08:00
    背包问题可以满足你
    burnbrid
        11
    burnbrid  
    OP
       2019-08-20 14:52:53 +08:00
    @noqwerty 哪个是你的代码? ID 是 麟渊 吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1805 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:30 · PVG 00:30 · LAX 09:30 · JFK 12:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.