r - 将数字组合成不超过最大值向量的最佳组的算法？

Question

我正在为我的房子切割饰条，有各种长度的饰条，我想对它们进行最佳分组，以尽量减少浪费。基本上，我正在尝试以最佳方式将所需长度分组(或打包)到可用的更长长度中。

我对如何处理这个问题有点困惑，目前只是手工完成，但一个错误最终导致我重新进行整个操作。我知道一些 java，但最近一直在专门使用 R，所以这是我目前最熟悉的语言。是否有关于如何解决这个问题的建议？

有没有比使用类似这样的算法手动循环更好的方法(我只是勾勒出这个想法；不要寻找正确的语法):

trim_lengths <- c(44, 57, 86, 86, 40, 88, 88, 41, 40, 40,
  62, 62, 54, 54, 55, 55, 63, 63, 75, 75, 100, 100)

avail_lengths <- c(120, 103, rep(100, 9), 98, rep(97, 4),
  95, rep(88, 3), 85, 65)

while(length(trim_lengths) > 0) {
  current_max <- max(trim_lengths)
  current_min <- min(trim_lengths)

  if(current_max + current_min > max(avail_lengths) {
    find smallest value in avail_lengths that's greater than current_max
    store current_max and optimal value from avail_lengths in list or vector
      to indicate the pairing/grouping
  }

  else {
    group <- c(current_max, current_min)
    current_max <- trim_lengths minux elements in group
    if <- sum(group) + current_max > max(avail_lengths) {
      store group and corresponding avail_length element in list/vector
    }

    else{
      basically, keep trying to group until solved
    }
  }

我已经知道这不是最优的，因为它是从 trim_lengths 向量上的“由外向内”检查，而我的手工配对通常最终会将一个小的和中等的值配对成一个可用的很容易看到的长度仅比所述配对长一两英寸。

无论如何，这是一个有趣的问题，我想知道是否有引用资料或明显的建议可以想到解决方案。在一些相关问题中，第一条评论经常会问“你尝试了什么”。我真的没有……因为我现在很困惑。我唯一想到的另一件事是随机强制组合，存储可最大限度减少浪费的解决方案。

我喜欢一些关于以矢量化方式解决这个问题的建议——某种矩阵运算，或者可能是问题的线性模型表示。我也会继续考虑的。

Answer 1

礼貌 http://xkcd.com/287/

(是的，这是评论，不是答案。如果只有 imgs 可以加载到小小的评论行中)