算法题：140 克盐如何 3 次分成 50 克、90 克？

01故事起源

有一个天平，7克、2克砝码各一个，如何只用这些物品三次将140克盐分成50g，90g各一份？

02

不用砝码的情况

天平是用于衡量是否相等，所以如果不借助砝码，只能等分。

如第一次分成70和70，第二次可以分成35和35，第三次可以等分35或者105。

但上面分出的数值，是无法组合成50或者90的。所以接下来就考虑借助砝码的情况。

03

借助砝码的情况

3.1方法一

砝码和盐各放一边，可以得到，克重量。

3.2方法二

砝码放一边，将克盐放两边，可以得到如下重量。

3.3方法三

砝码放两边，盐放一边或者两边。

这样就把所有的可能枚举完了，接下来就要看如果用这些方式组合成目标数。

04

用码组合

4.135克

前2步不用砝码可以得到35克，再结合砝码可以得到如下。

可以看到红色产生了15克，加上35克刚好50，这就有一个解。

4.270克

前1步不用砝码，能得到70克，再结合砝码。
称一次：

称二次：
根据上面一次的结果来看，盐放两边和砝放两边都无法再组合。但如果盐放一边可以多一个砝。
刚好发现如果先分成9+61。再用多的9+2来分61刚好得50，又得一个解。

4.3140克

一开始就借助砝码得到不同的重量，不过这个解很难直接看出来。

05

用砝码拼凑

如果按下面的方法称一次，就会得到相同重量的盐，所以也可以把右边的盐当成一个砝码，这样称三次就不只是2个砝码了。

接下来我们用这种方法，看能称出哪些重量的盐。

然后我们就要用这些数字，看能否组合成50或者90。
很容易可以发现下面的红色加起来刚好就是50。

也就是要4个2g的，和6个7g的。

如果用数学方法也可以得到上面的结论。
只有2个砝码，2克和7克的，如果用这2个来随意组合。
设个2克，个7克，即，整数解如下：

x	y
18	2
11	4
4	6

因为只能称三次，前两组解是无法组合出这么多的，所以得到。

5.1组合一

天平称一次，可以将重量翻一倍。上面砝码是分开的，次数不够，所以需要合并。
重新组合成。
那么最后一次要先得到，又得到一组解。具体过程如下：
第一次，第二次：

第三次：

5.2组合二

这组解也很难直接发现，因为要利用到砝码的5g差。

06

过程抽象

整个过程其实就是一个搜索的思路，DFS或者BFS，但我想用动态规划里面的语言来抽象描述一下。
初始条件：开局一个天平，2，7克砝码，140g盐。
决策：第2，3小节里，不用砝码，和借助砝码的多种方法。
阶段：总共称三次，每一次就是一个阶段。
状态：每过一个阶段，能得到的不同的情况。
状态转移：根据上面不同的决策转移到下一个状态。

07

总结

初始条件很简单，但决策很多，每过一个阶段，状态也会成倍的增加。而且阶段有3层，最后的状态数已经很多了，人工模拟还是比较难的。最好的方法还是参考4、5小节，看能否快速找到一个可行解。

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

推荐关注「算法爱好者」，修炼编程内功

点赞和在看就是最大的支持❤️