浮点数子集和问题的递归函数

Question

我为 subset sum problem 创建了一个递归函数 f(s,x)，当从值 x.

例如假设x <- c(2,4,8,10)，s <- 10表示目标和，下面的函数f

f <- function(s, x, xhead = head(x,1), r = c()) {
  if (s == 0) {
    return(list(r))
  } else {
    x <- sort(x,decreasing = T)
    return(unlist(lapply(x[x<=min(xhead,s)], function(k) f(s-k, x[x<= s-k], min(k,head(x[x<=s-k],1)), c(r,k))),recursive = F)) 
  }
}

我可以获得子集总和的所有组合，即

> f(s,x)
[[1]]
[1] 10

[[2]]
[1] 8 2

[[3]]
[1] 4 4 2

[[4]]
[1] 4 2 2 2

[[5]]
[1] 2 2 2 2 2

上面的函数适用于 x 和 s 的整数。但是，当我将x和s都缩小10时，即[=的浮点数15=] 和 s，然后输出变成不需要的：

> f(s/10,x/10)
[[1]]
[1] 1

但所需的输出应该像

> Map(function(v) v/10, f(s,x))
[[1]]
[1] 1

[[2]]
[1] 0.8 0.2

[[3]]
[1] 0.4 0.4 0.2

[[4]]
[1] 0.4 0.2 0.2 0.2

[[5]]
[1] 0.2 0.2 0.2 0.2 0.2

我怀疑我的函数f在处理浮点数时一定有问题，但试了几次都没有解决。任何人都可以帮我解决这个问题而不需要对函数 f 做大的改动吗？

提前感谢任何帮助！

Answer 1

您可以在减法中使用 round 并设置小数点

f <- function(s, x, xhead = head(x,1), r = c()) {
  if (s == 0) {
    return(list(r))
  } else {
    x <- sort(x,decreasing = T)
    return(unlist(lapply(x[x<=min(xhead,s)], function(k) f(round(s-k, 4), x[x<= round(s-k, 4)], min(k,head(x[x<= round(s-k, 4)],1)), c(r,k))),recursive = F)) 
  }
}

f(s/10,x/10)

其中 returns 所需的输出：

[[1]]
[1] 1

[[2]]
[1] 0.8 0.2

[[3]]
[1] 0.4 0.4 0.2

[[4]]
[1] 0.4 0.2 0.2 0.2

[[5]]
[1] 0.2 0.2 0.2 0.2 0.2

浮点数子集和问题的递归函数

recursive function for subset sum problem with floating-point numbers

precision

r

subset-sum