algorithm - 如何构造这个约束满足问题？

Question

这是我的问题的延续:https://math.stackexchange.com/questions/3278359/figuring-out-the-underlying-construction-of-a-final-set

要以更 CS 的方式重新发布问题，您将如何找到 A如果只给出 B ？

$ A = [ 1, 5, 10 ]
$ B = f(A)
$ B == [ 1, 5, 6, 10, 11, 15, 16 ]
(true)
$ B == { 1, 5, 10, 5+1, 10+1, 10+5, 10+5+1 }
(true)
$ solve(B)
[ 1, 5, 10 ]

f()从所有非空组合中找到一组唯一值。

自 A始终是 B 的子集，我假设可能有一种蛮力方法，您可以尝试 B 中的每种元素组合。 (这不是 B 的所有 元素，)直到您解决了整个集合。但是，这将是极其低效的。 (我在想象 N 阶阶乘之类的东西...)由于有多个解决方案，您要么需要计算整个集合，要么在某个阈值后停止。

经过评论中的一些讨论，我认为这是一个约束满足问题。这将如何构建？ (伪代码很好。)

对于 super 奖励积分:如果我们假设 A 不是 B 的子集，如何解决这个问题？

例如:

$ B = [15, 16, 15.5, .5, 10.5]
$ solve(B)
[.5, 1, 5, 10]

构建此问​​题的另一种方式:找到最小基值集的无损压缩算法是什么样的？ (基值和输出数据之间的映射可以忽略。)

Answer 1

如果 A 中的元素个数为 n ，则 B 中的元素个数为 (2^n) -1。
这意味着 B 中的元素数量等于 A 的所有可能子集的数量。

例如

如果 A={a,b,c}
那么 B={a,b,c,a+b,a+c,b+c,a+b+c}

为了得到B的所有元素，我们可以从1迭代到(2^n)-1。
现在我们将根据每个数字计算 B 的不同元素。

Let
A={a,b,c}.
n=3,Number of element in A

   For each i from 1 to 2^n-1, we will check each bit(j) of i from 0 to n-1.
   if jth bit is 1, we will take jth element of A for finding ith element of B.
   Such way we will add some number from A for finding ith element such that
   their index's bit in i is 1.

例如，

1   001     B[0]=a
2   010     B[1]=b
3   011     B[2]=a+b
4   100     B[3]=c
5   101     B[4]=a+c
6   110     B[5]=b+c
7   111     B[6]=a+b+c

因此总复杂度将为 n*2^n。

伪代码:

b=[]
for i in (from 1 to 2^n-1):
   ith=0
   for j in(from 0 to n-1)
       if(jth bit in i is 1)
           ith+=A[j]
   #inner_loop_end
   b.append(ith)