代码降临节 – 太多了 – 谜题 17

你好！我是Xavier Jouvenot，这是我关于Advent Of Code系列的长篇连载的第十七部分。你可以在这里找到上一部分。

对于这篇新文章，我们将解决2015年12月17日的问题，名为“永远不要嫌太多”。我将提出的解决方案是C++，但推理可以应用于其他语言。

第一部分

问题

这个问题的完整版本可以在Advent Of Code网站上直接找到，我在这里只描述问题的核心内容。

精灵们买的蛋酒太多了（150升），所以我们必须把它装进冰箱里的容器里。我们只想找出有多少种不同的容器组合可以正好装下全部150升蛋酒，并且所有容器都完全装满？

解决方案

有几种方法可以解决这个问题。

我的第一个想法是计算所有容器组合可以存储的体积。对于5个容器，它运行得很好，但是当我给它实际的输入，有20个容器时，执行时间就爆炸了。事实上，由于有太多的组合需要检查，我从未继续下去。

这次失败后，我尝试了第二种（也是更好）方法。这个解决方案包括一次放一个容器的蛋酒，然后检查是否还有剩余的蛋酒。如果有，再放进另一个容器，再检查，如果在任何时候，没有足够的蛋酒来装满容器，或者我们成功地完美地储存了蛋酒，那么，我们就去找下一个容器组合，这意味着递归（耶！\o/）。

但废话少说，让我们深入代码。实际上，会有一个主函数包含其中的算法。

<code class="language-c++">using Container = size_t;
using Containers = std::vector<Container>;

size_t countNumberOfCombination(const Containers &containers, size_t volum) {
  size_t numberOfCombination{0};
  for (auto index = size_t{0}; index < containers.size(); ++index) {
    const auto remainingVolum = volum - containers[index];
    if (remainingVolum == 0) {
      ++numberOfCombination;
      continue;
    }
    if (remainingVolum < 0) {
      continue;
    }
    Containers containersNotUsed;
    std::copy(containers.begin() + index + 1, containers.end(),
              std::back_inserter(containersNotUsed));

    numberOfCombination +=
        countNumberOfCombination(containersNotUsed, remainingVolum);
  }
  return numberOfCombination;
}
</code>

别担心，像往常一样，我会解释这段代码是如何工作的。

作为参数，我们有可用的容器和需要储存的蛋酒体积。对于每个容器，我们检查用蛋酒装满它是否能使蛋酒体积变为0，如果情况是这样，我们就成功了！我们找到了一个组合！但如果我们能用蛋酒完全装满容器，那么，我们就忽略这个容器，然后去找下一个。最后，如果我们能装满容器并且还有一些蛋酒剩余，那么，递归就来了，我们再次进行这些检查，但不包括这个容器和这个容器的蛋酒体积。一旦递归调用完成，我们将得到当前容器满载的组合数量，所以我们可以将这个数字加到当前已知的容器组合数量中。

我们所要做的就是给这个函数输入问题的数据，这样，我们就知道了有多少种容器组合

我鼓励你在我的GitHub上查看完整的解决方案

第二部分

问题

在这一部分，我们需要找出有多少种容器组合实际上可以包含150升蛋酒，并且使用最少的容器。

解决方案

为了解决这个问题，我决定修改用于第一部分的函数，使其看起来像这样：

<code class="language-c++">size_t countNumberOfCombination(const Containers &containers, size_t volum,
                                size_t numberOfContainerUsed,
                                size_t &numberMinOfContainerUsed) {
  size_t numberOfCombination{0};
  for (auto index = size_t{0}; index < containers.size(); ++index) {
    const int remainingVolum = volum - containers[index];
    if (remainingVolum == 0) {
      if (numberMinOfContainerUsed > (numberOfContainerUsed + 1)) {
        numberOfCombination = 1;
        numberMinOfContainerUsed = numberOfContainerUsed + 1;
      } else {
        assert(numberMinOfContainerUsed == (numberOfContainerUsed + 1));
        ++numberOfCombination;
      }
      continue;
    }
    if (remainingVolum < 0) {
      continue;
    }
    if ((numberOfContainerUsed + 1) >= numberMinOfContainerUsed) {
      continue;
    }
    Containers containersNotUsed;
    std::copy(containers.begin() + index + 1, containers.end(),
              std::back_inserter(containersNotUsed));

    const auto currentNumberMinOfContainerUsed = numberMinOfContainerUsed;

    const auto numberOfCombinationFound = countNumberOfCombination(
        containersNotUsed, remainingVolum, numberOfContainerUsed + 1,
        numberMinOfContainerUsed);
    if (currentNumberMinOfContainerUsed == numberMinOfContainerUsed) {
      numberOfCombination += numberOfCombinationFound;
    } else {
      numberOfCombination = numberOfCombinationFound;
    }
  }
  return numberOfCombination;
}
</code>

这比第一部分长了很多。让我们解释一下这些变化。

首先，有两个新的参数，用于跟踪递归过程中使用的容器数量。

然后，对组合进行了验证修改：

<code class="language-c++">if (remainingVolum == 0) {
    if (numberMinOfContainerUsed > (numberOfContainerUsed + 1)) {
        numberOfCombination = 1;
        numberMinOfContainerUsed = numberOfContainerUsed + 1;
    } else {
        assert(numberMinOfContainerUsed == (numberOfContainerUsed + 1));
        ++numberOfCombination;
    }
    continue;
}
</code>

在此，我们检查找到的组合是否比之前找到的组合使用的容器少。如果是，我们重置找到的组合数量并更新最小容器数。如果不是，那么，我们只需要增加找到的组合数量。

在递归之前，我们检查添加这个容器是否会使我们超过已经找到的最小值。如果是，我们直接跳到下一个容器。

最后，是递归：

<code class="language-c++">const auto currentNumberMinOfContainerUsed = numberMinOfContainerUsed;
const auto numberOfCombinationFound = countNumberOfCombination(
    containersNotUsed, remainingVolum, numberOfContainerUsed + 1,
    numberMinOfContainerUsed);
if (currentNumberMinOfContainerUsed == numberMinOfContainerUsed) {
    numberOfCombination += numberOfCombinationFound;
} else {
    numberOfCombination = numberOfCombinationFound;
}
</code>

这里，我们检查最小容器数量是否已更改。如果更改了，我们就将当前已知的组合数量更改为递归期间找到的数量；如果未更改，我们将找到的组合数量加到当前已知的数量中。

这样，我们就有了新的算法来解决我们的问题。

结论

你可以注意到，本文中提供的解决方案并未包含运行程序的全部源代码，而只包含了解决此问题相关的有趣部分。如果你想看到完整的程序，可以访问我的GitHub账户，探索完整解决方案，添加评论，或者在阅读本文的平台上提问，这将有助于我提高文章质量。

这里列出了我们使用的一些元素，我强烈建议你查看它们的定义。

• std::vector
• std::copy
• std::back_inserter

感谢你的阅读，希望你喜欢！

在下一部分之前，祝你学习愉快，不断成长。