算出A列数据中是B列数据中那几个数的之和（或B列数据几个数据之和近似值）

数据如下：

A <- c(11611.60,35000.00, 15527.20, 52972.00, 8434.00, 15000.00, 17908.00, 9211.80, 5850.00, 11663.60, 11674.00, 11206.00, 14852.00, 14333.80, 30500.00, 26952.00, 18925.52, 18472.00, 47762.48)

B <- c(11663.60,35000.00,15527.20, 52972.00, 8434.40, 15000.00, 17908.00, 9211.80, 17000.00, 10500.00,41000.00,13772.00, 5288.00, 4700.00, 4352.00, 14333.80, 26952.00, 11611.60, 11674.00, 3580.00,11206.00,3400.00,4850.00,12672.00)

我需要 找出  向量A 中的数 是 向量B 中的那几个数之和（也可以是近似值或是B中几个数相加之和 约等于A 中的数）；  求解 ？

fcfc2013 发表于 2018-9-19 23:00
惭愧！  看了半天 没看懂

本质上是个用判断条件来加速的遍历算法，学过堆栈的话容易理解

1. TARGET=18925.52 #要拟合的目标值
   
2. present=1 #present变量在循环过程中指示要在当前循环中压入堆栈的值的序号。初始化为1
   
3. stack=c(1) #stack是作为堆栈使用的向量，用序号表示当前循环到B里的哪几个数。初始化堆栈，把B里第一个数放到堆栈里
   
4. Len=length(B) #Len存放B的长度，也就是有几个数可以用来拟合。用一个变量来存只是为了方便后面调用
   
5. Min_difference=max(B) #用来存放搜索到的最小偏差数值。随便用了B里最大数来初始化
   
6. Items=c() #用来存放目前为止搜索到的最接近目标的B的子集，用序号表示B里的元素。
   
7. while(stack[1]!=Len){ #循环，终止条件为堆栈里的数已经是B里最后一个数。
   
8.   value=sum(B[stack]) #计算当前堆栈里的B的元素和，
   
9.   if(abs(value-TARGET)<Min_difference){ #如果与目标值的差比历史最小值小，
   
10.     Min_difference=abs(value-TARGET) #就把这个差记录下来、
    
11.     Items=stack #把这个堆栈（B的子集）也记录下来。
    
12.   }
    
13.   if(present==Len){ #1.如果现在这次循环压入堆栈的是B的最后一个数，那么需要后退：不仅需要把这个数从堆栈扔掉，还要把堆栈倒数第二个数换成下一个。
    
14.     present=stack[length(stack)-1]+1 #（下一个要压入堆栈的应该是现在堆栈里倒数第二个数在B的下一个数、）
    
15.     stack=stack[c(-length(stack),-(length(stack)-1))] #（把堆栈最后的两个数扔掉。）
    
16.   }else{ #2.如果现在这次循环压入堆栈的不是B的最后一个数，那么还不需要后退，但也要分情况；
    
17.     if(value >TARGET){ #2.1如果当前子集的和已经超过目标值，再加新的数只会距离目标更远，所以直接把堆栈里最后一个数换成B的下一个
    
18.       present=stack[length(stack)]+1 #（下一个要压入堆栈的是现在堆栈里最后一个数在B的下一个数、）
    
19.       stack=stack[-length(stack)] #（把堆栈最后一个数扔掉。）
    
20.     }else{ #2.2如果当前子集的和还没超过目标值，尝试增加B下一个新的数进堆栈里。
    
21.       present=stack[length(stack)]+1 #（下一个要压入堆栈的是现在堆栈里最后一个数在B的下一个数。）
    
22.     }
    
23.   }
    
24.   stack=c(stack,present) #把要压进堆栈里的数压进堆栈。然后循环
    
25. }
    
26. result=list(ERROR=Min_difference,INDEXs=Items,ITEMs=B[Items]) #输出结果。ERROR是和目标的偏差值，INEDXs是子集里元素在B的序号，ITEMs是子集里的元素值

复制代码

fcfc2013 发表于 2018-9-12 16:50
数据如下：

A

此贴无大神理会？
我的思路：<br>
二列数据编号，依次比较 <- A$1 >= B$1 ，再 将比较后比A$1 小的 数（应该是个向量） <br>
二二想加<br>
sun（B$1，B$2）<br>
sun（B$2，B$3）<br>
  再比较。  <br>
B$11 == A1；<br>
B$12 == A1，<br>
或是： 将B列数据 想加后得到一个矩阵，查找矩阵中数 == A列中的数， 如有相等，返回 那个数 是B列中那几个数相加。

用堆栈做，写得

1. TARGET=18925.52
   
2. present=1;stack=c(1);Len=length(B);Min_difference=max(B);Items=c()
   
3. while(stack[1]!=Len){
   
4.   value=sum(B[stack])
   
5.   if(abs(value-TARGET)<Min_difference){
   
6.     Min_difference=abs(value-TARGET)
   
7.     Items=stack
   
8.   }
   
9.   if(present==Len){
   
10.     present=stack[length(stack)-1]+1
    
11.     stack=stack[c(-length(stack),-(length(stack)-1))]
    
12.   }else{
    
13.     if(value >TARGET){
    
14.       present=stack[length(stack)]+1
    
15.       stack=stack[-length(stack)]
    
16.     }else{
    
17.       present=stack[length(stack)]+1
    
18.     }
    
19.   }
    
20.   stack=c(stack,present)
    
21. }
    
22. result=list(ERROR=Min_difference,INDEXs=Items,ITEMs=B[Items])

复制代码

自己封一个函数调用吧

思路上是把B里的数按顺序压进栈里，每次都计算差值，并和最小差异比较。如果有一个数压进去之后超过目标值，那后续的值都不用试了只会越来越远，所以把这个数扔了换下一个数；如果没有超过目标值，就保留目前堆栈并把下一个数压进栈里。如果是最后一个数被压进了栈里，就把倒数第二个数扔了换成下一个数。
直到栈里唯一的一个数是最末的那个数为止，结束，输出结果

fdsasdfddsa 发表于 2018-9-17 20:48
用堆栈做，写得

自己封一个函数调用吧

  惭愧！  看了半天 没看懂

此问题，就是一个线性（非负整数）规划：
A ：y1,y2,....,ym
  B:  x1,x2,... ,xn
##
   y1=a11*x1+a12*x2+...+ a1n*xn
   y2=a21*x1+a22*x2+...+a2n*xn
   ......................
   ym=am1*x1+am2*x2+...amn*xn
### 简写距阵为
   y =a*x    ## 即距阵求逆，但
   要求 系数  aij  为 0，或 1
    在R 中不难找到此类计算的函数。。或自已用R中提供的距阵运算，自已设计一下，也不难吧
                                                      

fdsasdfddsa 发表于 2018-9-20 20:43
本质上是个用判断条件来加速的遍历算法，学过堆栈的话容易理解

谢谢，解答的详细。

jgchen1966 发表于 2018-9-21 12:00
此问题，就是一个线性（非负整数）规划：
A ：y1,y2,....,ym
  B:  x1,x2,... ,xn

我用Excel 的 规划求解 功能 是可以 解决， 但一个个的手动计算 还是很麻烦， 这是证明 你提供的思路可行。
在R中还没试过 用线性求解；  
你能根据上面数据，写个参考R代码，测试下求解？

jgchen1966 发表于 2018-9-21 12:00
此问题，就是一个线性（非负整数）规划：
A ：y1,y2,....,ym
  B:  x1,x2,... ,xn

library(Rglpk)
# 5*x+4*x+3*x+3*x = 9<br>
# 约束条件： x &lt;= 0,1 int
obj &lt;- c(1, 0)<br>
mat &lt;- matrix(c(5, 4, 3, 3),1,4,T)<br>
dir &lt;- c(\"==\")<br>
rhs &lt;- c(9)
Rglpk_solve_LP(obj, mat, dir, rhs)<br>
解上面的方程， 用Rlpk包   ，下面代码写法不对吗？