下料优化:在R中寻找所有可能的组合

Question

我正在研究here中描述的切割库存问题。现在问题的起点是，对于给定的可能切割，即14,31,36,45，长度为100的木板可以被切割成37种可能的模式。一种模式可以是1,0,1,1，而另一种模式可以是1,1,0,1或0,0,0,2等等。是否存在可以在R中使用的现有算法，该算法将列出给定的所有大小和单个切割的所有可能的组合在这种情况下37

Answer 1

这是一种暴力的方法。创建一个对每个切割都有"max“的向量。然后创建一个可能性网格。然后在网格上对切割进行矩阵乘法，得到组合的总“长度”--任何小于或等于(lteq) 100的值都是“合法的”。注意有38个组合，因为有一个案例是0,0,0,0，你可能想要丢弃它。

cuts <- c(14, 31, 36, 45)
# Get the max number of each length of cut
max_of_each <- floor(100 / cuts)  

possibilities <- lapply(max_of_each, function(i) seq(0, i))
grid_possibilities <- expand.grid(possibilities)
idx_lteq_100 <- as.matrix(grid_possibilities) %*% cuts <= 100

grid_possibilities[idx_lteq_100, ]
nrow(grid_possibilities[idx_lteq_100, ])
# [1] 38