难题！难题！算法(多个数据找目标值)

2018-5-4 22:12

M个数要求其中一个或多个想加找出目标数，并给出是由那几个数组成。
例如10个篮子，清空后打捞鱼，打捞完成
必定每个篮子里数是不确定的。
我需要x条鱼
计算，那几个篮子里的鱼数想加正好是我需要的数量
并给出由那几个篮子组成。
希望大虾们不吝赐教！谢了

2018-5-4 23:01

哈哈，这是个经典问题，专门登陆来回帖。
这个问题除了分步穷举，没有别的方法。
先计算所有两两相加的数，保存两个数和结果的对应关系，
然后排序，再计算一次，得到4个数的和，类似可以得到8个数的和
于是你有了，1，2，4，8，，个数相加的结果
需要几个数相加，就算出所有结果，然后看满足条件不，结果不一定存在的，也可能有好几组

2018-5-5 06:49

有没有历程，谢谢你给的思路

2018-5-5 08:51

网上搜索穷举法时间太慢，

2018-5-5 09:42

你肯出钱的话给你写一个

2018-5-5 13:08

那也得报个价呀

2018-5-5 15:10

1k打工钱

2018-5-5 21:23

比淘宝都贵

2018-5-5 21:25

不过可以接受，等客户下了决定，你负责这个算法的程序

2018-5-5 22:42

如果不需要优化算法，只需进行简单矩阵运算。特别适合DSP，有MAC指令的MCU，超快
未优化时计算次数是 2^M-1 次MAC。如果篮子太多，优化则有必要，先排除不必要的向量空间。
假设答案使用Mbit 向量表示。1表示对应篮子在答案组合之中，0 则否之

2018-5-5 23:13

1，先按照篮子中鱼的数量排序生成序列ai方便后续计算，并保留映射表，答案输出时逆变换回来。
2, 计算sum = ∑ai ；如果sum <x 无解，退出，sum=x，有唯一解，输出 2^M-1;
2; over= sum-x；将ai=M找出，生成答案输出 (2^M-1) =2^i；
3，将 ai<over 的映射生成一个序列bi,序列数为N，有可能小于M，可以减轻运算量。ai>over 为答案之中必然之选，输出答案时对应位均为1；
4；最笨的方法如下
for （i=1;i<2N-1；i++）
{
if （【bi】x【i】 ==over）输出答案；
}

2018-5-6 06:54

太谢谢了，论坛就该这样，给出思路

2018-5-6 13:36

代码写出来了：

编译成功：

调用方法：输入数据存在data.txt里面，目标和为96，结果输出在log.txt中
TIM截图20180506132953.png

输入数据示例：

输出数据示例：

2018-5-6 21:35

来来来，讲讲这类算法的另一个应用
M定义成2097152个200bit长的随机数，N定义成512，加法简化成异或
目标是找出512个数，使得这512个数异或之后的结果为200bit的0
这个算法用于ZCASH挖矿，每天都产值在几千万元*币，按现在价格计算是一天一千万元
还有一种简单点的，M定义成65536个96bit的数，N定义成32，还是异或
目标是从65536个96bit数中，找出32个数，使他们异或之后的结果为96bit的0，一天也有几十万元

2018-5-7 09:05

xxzouzhichao 发表于 2018-5-6 13:36
代码写出来了：
编译成功：

厉害了，膜拜

2018-5-7 17:44

建议你去计算机网站发一下.肯定就不是这个结果了. ....
要是穷举,那就不会有人问这个问题了.
这个题还缺一个条件,要求篮子最少.

2018-5-8 09:17

对，去CSDN发帖问问吧。

2018-5-8 13:41

icecut 发表于 2018-5-7 17:44
建议你去计算机网站发一下.肯定就不是这个结果了. ....
要是穷举,那就不会有人问这个问题了.
这个题还缺一 ...

老i，先试一个的，再试任意两个的，然后5s到了，可以从矿坑刷下个要计算的数了。
内存只能这么大了。

2018-5-8 14:21

linqing171 发表于 2018-5-8 13:41
老i，先试一个的，再试任意两个的，然后5s到了，可以从矿坑刷下个要计算的数了。
内存只能这么大了。 ...

对的, 广度优先搜索.

专栏首页

难题！难题！算法(多个数据找目标值)

相关下载

相关帖子

甘甜之泉水

技术新星奖章

常驻人口

无冕之王奖章

沉静之湖泊

十世金身

技术导师奖章

缘定三生

技术奇才奖章

技术领袖奖章

荣誉元老奖章

坚毅之洋流

技术高手奖章

以坛为家