r - 在 R 中实现优化的二维子集和问题

Question

我正在处理众所周知的子集和问题的变体，我真的需要一些帮助。在我的问题中，我有一个m包含两列（a、b）和n行的矩阵。我想找到对应的a和b值的总和等于两个目标值 ( a_target, b_target) 的行。一些约束是 , a_target, b_target,a都是b完整的正整数，我只对满足返回的两个目标的标准的第一个解决方案感兴趣，或者如果没有解决方案符合标准，则最接近。这个最接近的可以定义为两个目标的误差之和。由于此方法将在大型数据集上运行，因此我需要优化解决方案。

问题可以设置如下：

m <- matrix(data=sample(1:100, 200, replace=T),
            ncol=2,
            dimnames = list(
              NULL,c("a","b")
            ))
head(m)
      a  b
[1,] 44 80
[2,] 51 24
[3,] 31 68
[4,] 46 55
[5,] 34 98
[6,] 93 49

a_target <- 500 
b_target <- 700 

为了给出一些背景知识，普通的子集和问题涉及找到一组整数的任何子集，这些子集总和为某个目标t，这是 NP 完全的。有多种方法可以通过不同的时间优化来做到这一点。subsetsumR 中的一个这样的包是文档。我已经从这个包中获取了代码，目的是修改它以用于我的问题，但我不确定它是否可能，例如这个解决方案需要t按递增顺序工作，所以我不确定它的适用性如何将有两个t值。t 为单列即向量的代码为：

subsetsum <- function(S, t) {
  n <- length(S)
  inds <- NULL
  x <- logical(n)
  F <- numeric(t + 1)
  G <- logical(t + 1)
  G[1] <- TRUE
  print(paste("n,inds,x,F,G",n,inds,x,F,G))  
  for (k in 1:n) {
      H <- c(logical(S[k]), G[1:(t + 1 - S[k])])
      H <- (G < H)
      j <- which(H)
      F[j] <- k
      G[j] <- TRUE
      if (G[t + 1]) break
  }
  wch <- which(G)
  j <- wch[length(wch)]
  fmax <- j - 1
  while (j > 1) {
      k <- F[j]
      x[k] <- TRUE
      j <- j - S[k]
  }
  inds <- which(x)
  
  return(list(val = sum(S[inds]), inds = inds))
}

标签： rdynamic-programmingsubset-sum