这是一个创建于 1947 天前的主题，其中的信息可能已经有所发展或是发生改变。
算法-在一组数中，把相加之和最近 100 的数，提取出来。 举个例子:
1 3 90 2 8 96 在这组数中应该把 96 和 3 这个俩个数提取出来。
1 2 3 8 96 99 在这组数中应该把 99 这一个数提取出来。
大神帮帮忙，我支持香港警察，你们可以帮我了。
 |
1
maichael 2019-08-20 09:17:53 +08:00
你这题有歧义呀，能提 1 个和 2 个，是不是还能提 3 个 4 个？限制条件不够。
|
 |
2
burnbrid OP @maichael 是可以提取多个数字，其实我的目的就是从一个池子里面抓钱，要尽可能的多抓钱。但是，抓的钱最多不能超过或等于 100 块。
|
|
3
maichael 2019-08-20 09:24:14 +08:00
@burnbrid #2 那你第一个例子里面，即可以选 90+8+1,也可以选 96+3，也可以选 96+3+1。答案也可以多个解吗？
|
 |
5
misaka19000 2019-08-20 09:27:05 +08:00 via Android
动态规划吧
|
|
6
misaka19000 2019-08-20 09:27:52 +08:00 via Android
动态规划
|
|
7
burnbrid OP @maichael 是的，提取几个数字无所谓，最关键是不能超过 100 块。可以提取多个数字，也可以提取一个数字。其实我的目的就是从一个池子里面抓钱，要尽可能的多抓钱。但是，抓的钱最多不能超过或等于 100 块，至于你抓多少张钱我不关心，我关心的是抓的钱要尽可能接近 100 块但不能超过 100 块，。
|
 |
8
ytmsdy 2019-08-20 09:36:07 +08:00
f(x) = x_number +f(x -x_number)
x_number：数组中第一个小于 x 的数字 |
 |
9
louiswang002 2019-08-20 09:38:20 +08:00 via iPhone
动态规划-宝石谜题
|
 |
10
ahaxzh 2019-08-20 09:44:18 +08:00
dp
|
 |
11
ylsc633 2019-08-20 09:53:35 +08:00
粗略一想 贪心算法
又想了下,贪心算法不正常 那就动态规划了 |
 |
12
finalwave 2019-08-20 10:02:16 +08:00
这不就是个容量 100 的背包问题，最多能塞多少
|
 |
13
kkeiko 2019-08-20 10:16:23 +08:00
简单的思路：排序，头尾双指针，往中间走。复杂度 O(nlogn)
进阶一点：动态规划，复杂度 O(n) |
 |
14
wqzjk393 2019-08-20 10:23:20 +08:00
盲猜一个。。
先 sort 一遍。 定义一个余数变量初始为 100。遍历一遍数组，每遍历一个数令余数=（余数-当前数），然后在数组中小于余数的部分中再次遍历。每当余数-当前数小于 0 或者遍历完以后停止遍历，把余数和遍历到的数分别放进两个数组中。比较余数，然后找对应位置的遍历结果就是答案了。。 |
 |
15
kkk0406 2019-08-20 10:24:58 +08:00
动态规划 背包问题
|
 |
16
antipro 2019-08-20 10:28:16 +08:00 via Android
我想到一个简单办法，把这组数中所有可能的组合列出来各自求合，再做个倒序排序，最接近 100 的数字对应的组合就是你要的答案了，当然可能会有多个解。
|
Select Language