算法思路——梅氏砝码问题

夜雨微澜

最近在研究这个问题，发现网上的讲解要么只讲算法不讲算理，要么不明不白。我总结了这类问题的解决思路，以及为什么使用这种方法来解决。
题目类似是这样的：
一位商人有一个40磅的砝码，由于跌落在地而碎成4块.后来，称得每块碎片的重量都是整磅数，而且可以用这4块来称从1至40磅之间的任意整数磅的重物.
问这4块砝码碎片各重多少？
上面只是一个示例。真实的题目其中总质量不一定是40，数量也不一定是4。
称法有三种：
1、一边只有物体，另一边只有砝码：此时物体的质量等于砝码的质量之和；
2、一边只有砝码，另一边同时有物体和砝码：此时物体的质量等于只有砝码的一侧砝码质量之和减去有物体的一侧砝码质量之和；
3、两侧都同时有砝码和物体：这种情况可以通过两边减去相同质量的物体直至某一侧物体减完来转换为情况1或2，故不讨论。
那么，质量为1磅的砝码存不存在呢？
对于39磅的物体，想要称量它，只能采用称法1（因为若使用称法2，则有a和b使得a+b=40且a-b=39，但解得a，b分别为39.5和0.5，不符合题目中砝码的质量是整数的要求）。即有若干块砝码的质量和是39磅，又因为总40磅，那么一定有一块砝码质量为1磅。
对于能称量1-n磅的砝码或者砝码组合，有以下规律：
若添加一个质量为2n+1的砝码，则可称量1-3n+1的所有整数质量。
很好理解。对于[n+1,2n+1]范围内的质量，保证一个盘内只有质量为2n+1的砝码，另一个盘内有物品和能称量1-n磅的砝码或者砝码组合中的一个或者多个砝码，通过增减物品盘内的砝码质量即可。这使用了上面所说的称法2。
对于[2n+2,3n+1]范围内的质量，使用称法1，保证2n+1的砝码在砝码盘内，通过调节其他砝码即可。
因此不难得出下一个砝码的质量为3。通过1和3两个砝码，最多可以称出4。那么下一个砝码质量为9…………以此类推，编程实现即可。

刺心

为了确定碎成的每块砝码的重量，并能称量从1到总重量之间的所有整数重量，可以使用一种叫做三进制的思路。三进制的特点是可以通过多种组合称量不同的重量。在这种情况下，砝码的重量需要符合一定的规律。具体地：

假设总重量为 W，砝码的数量为 n。  【论坛没办法展示𝑊和𝑛】

根据题目的约束条件，使用以下方法来寻找最优解：

三进制思路：每个砝码的重量应该满足三进制的规律，即每个砝码的重量为前一个砝码重量的三倍加一。这样，可以通过组合称量不同的重量。

验证每个砝码的重量：首先确定第一个砝码的重量，然后依次计算出其他砝码的重量，并验证能否称量从1到总重量之间的所有重量。

举例说明（题目中的示例）：

假设总重量为40磅，砝码数量为4。根据三进制规律，每个砝码的重量依次为：
1,3,9,27

通过这些砝码的组合，可以称量从1到40之间的所有重量。例如：

        称量1磅：直接使用1磅的砝码。
        称量2磅：使用3磅的砝码减去1磅的砝码。
        称量3磅：直接使用3磅的砝码。
        称量4磅：使用3磅和1磅的砝码。
        称量5磅：使用9磅的砝码减去4磅的砝码。
……以此类推。

编程实现方面，可以用递归或者迭代的方法生成砝码组合，并验证其有效性。

以下是一个Python代码示例，展示如何生成砝码组合并验证其有效性：

[Python] 纯文本查看 复制代码

def generate_weights(total_weight, num_weights):
    # 生成符合三进制规律的砝码重量
    weights = []  # 初始化空列表，用于存储砝码重量
    current_weight = 1  # 第一个砝码的重量为1
    while len(weights) < num_weights:
        weights.append(current_weight)  # 将当前重量添加到列表中
        current_weight *= 3  # 更新当前重量为其三倍
    return weights  # 返回生成的砝码重量列表

def can_measure_all(weights, total_weight):
    # 验证这些砝码是否能够称量从1到total_weight之间的所有重量
    possible_weights = set()  # 使用集合来存储所有可能的称量结果
    
    def measure(weights, index, current_sum):
        # 递归函数，用于计算可能的称量结果
        if index == len(weights):
            return  # 如果已处理完所有砝码，返回
        possible_weights.add(current_sum + weights[index])  # 添加当前和+当前砝码重量的结果
        possible_weights.add(abs(current_sum - weights[index]))  # 添加当前和-当前砝码重量的结果
        measure(weights, index + 1, current_sum + weights[index])  # 递归调用，处理下一个砝码
        measure(weights, index + 1, abs(current_sum - weights[index]))  # 递归调用，处理下一个砝码

    measure(weights, 0, 0)  # 初始调用递归函数，开始计算可能的称量结果
    
    for i in range(1, total_weight + 1):
        # 检查1到total_weight之间的每个重量是否都在可能的称量结果中
        if i not in possible_weights:
            return False  # 如果有一个重量无法称量，返回False
    return True  # 如果所有重量都能称量，返回True

def find_optimal_weights(total_weight, num_weights):
    # 找到最优的砝码组合
    weights = generate_weights(total_weight, num_weights)  # 生成砝码重量
    if can_measure_all(weights, total_weight):
        return weights  # 如果这些砝码能称量所有重量，返回砝码列表
    else:
        return None  # 否则返回None

# 示例
total_weight = 40  # 总重量
num_weights = 4  # 砝码数量
optimal_weights = find_optimal_weights(total_weight, num_weights)  # 找到最优砝码组合

if optimal_weights:
    print(f"最优砝码组合为：{optimal_weights}")  # 输出最优砝码组合
else:
    print("无法找到符合条件的砝码组合。")  # 提示无法找到符合条件的砝码组合

运行结果会显示：

[Python] 纯文本查看 复制代码

最优砝码组合为：[1, 3, 9, 27]

这段代码首先生成符合三进制规律的砝码重量，然后验证这些砝码是否能够称量从1到总重量之间的所有重量。如果能，则输出最优砝码组合；否则提示无法找到符合条件的砝码组合。

jy262832680

看不懂 很厉害

cyxnzb

刺心 发表于 2024-7-19 18:09
为了确定碎成的每块砝码的重量，并能称量从1到总重量之间的所有整数重量，可以使用一种叫做三进制的思路。 ...

AI生成的？

mmbbyynn

感谢分享

SoftCracker

没听过这种算法

lastmu

很厉害。