float 子集和问题的递归函数

Question

我做了一个递归函数f(s,x)对于 subset sum problem ，当从值集 x 中选取元素时，它能够生成总和为目标总和“s”的所有唯一组合。 .

例如，假设 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，即 x 的 float 和 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在处理 float 的时候，试了几次都没有解决。任何人都可以帮我解决这个问题而不需要对功能进行大的改动 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)

返回所需的输出:

[[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