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

只看该作者 · 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

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

1万 · 2018-5-5 22:42

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

1万 · 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中

输入数据示例：

输出数据示例：

只看该作者 · 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，一天也有几十万元