algorithm - 怎么解释 "exact cover "的意思

Question

我想向没有任何数学背景的同事解释精确覆盖问题。我想向他们解释它可以在哪里使用以及如何使用？所以我的问题是这样的:我怎样才能向没有数学背景的人或者更确切地说是 child 解释确切的覆盖问题并使其更有趣和直观？有了这个我也想解释 P-NP(一般) 的概念。

Answer 1

我认为这里的一个很好的类比是拼图。

假设您要覆盖地板上的一个正方形，而不是常规设置，即您有确切的数量和形状来覆盖它一次并且它们都以某种方式适合，您有足够的 block 来多次覆盖。

问题是找到一堆碎片:
A. 它们都适合(没有重叠，没有间隙)。
B. 它们覆盖了正确的表面积(您拥有的正方形)。