示例,我现在有两个货柜A和B,里面装的都是相同的东西梳理分别为30和20

| 货柜 | 数量 |
|------|------|
| A | 30 |
| B | 20 |

现在要将货柜A和B中的货都发出去,已知到一共发了7个批次,每次发货数量如下
| 数量 |
|------|
| 4 |
| 6 |
| 6 |
| 7 |
| 8 |
| 9 |
| 10 |

只知道每次发的数量,不知道从哪个货柜发的。需要根据每次发货的数量进行拼凑,给每此发货添加一个来源货柜
保证来源货柜的总和A、B相同即可,不用考虑发货顺序。比如得到的结果是

| 数量 | 来源货柜 |
|------|---------|
| 4 | A |
| 6 | B |
| 6 | B |
| 7 | A |
| 8 | B |
| 9 | A |
| 10 | A |

也可以是
| 数量 | 来源货柜 |
|------|---------|
| 4 | B |
| 6 | B |
| 6 | A |
| 7 | A |
| 8 | A |
| 9 | A |
| 10 | B |

只要任意能组合成功,都可以

鉴于解空间才128,那直接穷举吧…

# 两个箱子
v = c("A", "B")

#  批次货物数
batch = c(4, 6, 6, 7, 8, 9, 10)

# 穷举128解空间 每一行Var1~Var7代表七个批次对应的货柜

dfcandidate = expand.grid(v, v, v, v, v, v, v, stringsAsFactors = FALSE)

# 筛选符合条件的解,即A柜数量刚好30
dfcandidate$result = apply(dfcandidate, 1, function(v) {
  batch_in_a = sum(batch[v == "A"])==30
})

# 输出解
dfcandidate[dfcandidate$result,]
#>    Var1 Var2 Var3 Var4 Var5 Var6 Var7 result
#> 23    A    B    B    A    B    A    A   TRUE
#> 42    B    A    A    B    A    B    A   TRUE
#> 68    B    B    A    A    A    A    B   TRUE
#> 70    B    A    B    A    A    A    B   TRUE

Created on 2023-09-22 with reprex v2.0.2

# 两个箱子
v = c(A = 1, B = 0)

# 批次货物数
Y = c(4, 6, 6, 7, 8, 9, 10)

# 各种可能组合
X = expand.grid(v, v, v, v, v, v, v)

# 筛选符合条件的组合
X[as.matrix(X) %*% Y == 30, ]
#>    Var1 Var2 Var3 Var4 Var5 Var6 Var7
#> 23    1    0    0    1    0    1    1
#> 42    0    1    1    0    1    0    1
#> 68    0    0    1    1    1    1    0
#> 70    0    1    0    1    1    1    0

<sup>Created on 2023-09-22 with reprex v2.0.2</sup>

X = expand.grid(v, v, v, v, v, v, v)

换成下面的代码更优雅点。

X = do.call(expand.grid, replicate(length(Y), v, simplify = FALSE))

可以用 R6 写一个模拟框架,可能更贴近楼主所说的“检查源头”的意思:

library(R6)

CargoSimulator <- R6Class(
  "CargoSimulator",
  private = list(
    cargo_A = 30,
    cargo_B = 20,
    shipments = c(4, 6, 6, 7, 8, 9, 10),
    trace = data.frame()
  ),
  public = list(
    initialize = function() {
      private$trace <- data.frame(Quantity = private$shipments, Source = NA)
    },
    trace_source = function() {
      backtrack <- function(index) {
        if (index > nrow(private$trace)) {
          return(TRUE)
        }

        qty <- private$trace$Quantity[index]
        sources <- sample(c("A", "B"))

        for (source in sources) {
          if (source == "A" && private$cargo_A >= qty) {
            private$cargo_A <- private$cargo_A - qty
            private$trace$Source[index] <- "A"

            if (backtrack(index + 1)) {
              return(TRUE)
            }

            private$cargo_A <- private$cargo_A + qty # backtrack
          } else if (source == "B" && private$cargo_B >= qty) {
            private$cargo_B <- private$cargo_B - qty
            private$trace$Source[index] <- "B"

            if (backtrack(index + 1)) {
              return(TRUE)
            }

            private$cargo_B <- private$cargo_B + qty # backtrack
          }
        }

        private$trace$Source[index] <- NA # backtrack
        return(FALSE)
      }

      if (backtrack(1)) {
        return(private$trace)
      } else {
        warning("No valid configuration found.")
        return(NULL)
      }
    }
  )
)

unique_config <- list()

for (i in 1:10000) {
  simulator <- CargoSimulator$new()
  config <- simulator$trace_source()
  if (!is.null(config)) {
    if (!any(sapply(unique_config, identical, config))) {
      unique_config[[length(unique_config) + 1]] <- config
    }
  }
}

unique_config
3 个月 后