蓝桥杯-砝码称重

2026-03-20 暂无评论

全文共 154 字，阅读约 1 分钟

2021蓝桥杯省赛 - 砝码操作

砝码称重

问题描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, ..., WN。
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 W1, W2, ..., WN。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

参考答案

# 蓝桥杯 - 砝码称重
n = int(input())
nums = list(map(int, input().split()))

# 使用集合存储所有可能的重量值，初始化为 0
s = set()
s.add(0)

# 遍历每个砝码，计算加入该砝码后所有可能的重量组合
for i in nums:
    for j in list(s):       # 遍历当前所有能称出的重量
        s.add(i + j)        # 把新砝码放左边（+）
        s.add(abs(i - j))   # 把新砝码放右边（-），用 abs 是因为重量取正
# 输出不同重量值的数量（排除初始的 0）
print(len(s) - 1)

另外本题可以使用DFS暴力搜索，代码如下：

import os
import sys
from functools import lru_cache

# 请在此输入您的代码
n = int(input())
nums = list(map(int, input().split()))

total = sum(nums)
ans = set()

@lru_cache(maxsize=None)
def dfs(idx, cur):
    if idx == n:
        if cur > 0:
            ans.add(cur)
        return
    dfs(idx + 1, cur)               # 不放
    dfs(idx + 1, cur + nums[idx])   # 放左边
    dfs(idx + 1, cur - nums[idx])   # 放右边

dfs(0, 0)
print(len(ans))