题目描述 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。 输入 输入的第一行包含一个整数 N。 第二行包含 N 个整数：W1, W2, W3, · · · , WN。 输出 输出一个整数代表答案。用python实现

可以使用动态规划来解决这个问题。

假设当前有 i 个砝码，已经称出了 j 种重量，考虑第 i+1 个砝码的贡献：

1. 不放在天平上，此时已经称出的重量种数不变，即 dp[i+1][j] = dp[i][j]；
2. 放在天平左边，此时已经称出的重量种数增加，即 dp[i+1][j+wi] = 1，其中 wi 表示第 i+1 个砝码的重量；
3. 放在天平右边，同理，即 dp[i+1][abs(j-wi)] = 1。

最终的答案就是 dp[N][0] + dp[N][1] + ... + dp[N][sum(W)]。

代码实现如下：

n = int(input())
w = list(map(int, input().split()))

max_sum = sum(w)
dp = [[0] * (max_sum+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
for j in range(max_sum+1):
dp[i+1][j] = dp[i][j]
if j >= w[i]:
dp[i+1][j] |= dp[i][j-w[i]]
dp[i+1][j-w[i]] |= dp[i][j]

print(sum(dp[n]))

相关问题

你有一架天平和 n 个砝码，这 n 个砝码重量依次是 w1, w2, · · · , wn。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

题目描述：你有一架天平和 n 个砝码，这 n 个砝码重量依次是 w1, w2, ···, wn。请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。

解题思路：根据题目，可以将砝码放置在天平的两边，所以实际上重量的种类可以从 0 开始计算，每次增加一个砝码可以得到新的重量种类。

举例说明：当只有一个砝码时，重量种类为 2，分别为 0 和该砝码的重量。当有两个砝码时，可以分为以下情况：

1.两个砝码重量相等，重量种类加 1，即前面一个砝码和后面一个砝码分别放在天平两边；
2.两个砝码重量不相等，可以得到两种新的重量种类：一种是前面一个砝码比后面一个砝码重，所以将前面一个砝码放在天平左边，后面一个砝码放在天平右边，得到一种新的重量；另一种是前面一个砝码比后面一个砝码轻，所以将前面一个砝码放在天平右边，后面一个砝码放在天平左边，得到另一种新的重量。

由此可得，当有 n 个砝码时，重量种类为：

1.当只有一个砝码时，重量种类为 2；
2.当有两个砝码时，重量种类为 2 + 2；
3.当有三个砝码时，重量种类为 2 + 2 + 4；
4.当有四个砝码时，重量种类为 2 + 2 + 4 + 8；
5. ……

由此可见，每增加一个砝码，重量种类会增加一个倍数，具体倍数可以通过递推得到。

解题代码：

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN 。 请你计算一共可以称出多少种不同的正整数重量？ 注意砝码可以放在天平两边。

假设天平左边的砝码重量总和为 $s$，右边的砝码重量总和为 $t$，则天平所称出的重量为 $|s-t|$。

如果每个砝码只能放在一侧，那么一共可以称出 $2^N$ 种不同的重量，因为每个砝码都有两种放置方式：放在左边或者放在右边。

但是，如果一个砝码可以同时放在左右两侧，那么就会出现重量相等的情况。为了避免重复计算，我们需要去除这些重复的情况。

假设存在一组砝码重量 $w_i$ 和 $w_j$，它们可以同时放在左右两侧。那么我们可以把它们看作是一个重量为 $w_i+w_j$ 的新砝码，只不过这个新砝码可以同时放在左右两侧。

因此，我们可以把所有可以同时放在左右两侧的砝码合并成一个砝码，然后再按照每个砝码只能放在一侧的方式计算总共可以称出多少种不同的重量。

具体来说，我们可以使用动态规划的思想，设 $f(i,j)$ 表示前 $i$ 个砝码可以称出的重量是否包括 $j$，如果包括则为 $1$，否则为 $0$。状态转移方程为：

$$f(i,j)=f(i-1,j)\text{ or }f(i-1,j-w_i)\text{ or }f(i-1,j+w_i)$$

其中 $\text{or}$ 表示逻辑或运算符。也就是说，前 $i$ 个砝码可以称出重量 $j$ 的条件是：前 $i-1$ 个砝码可以称出重量 $j$，或者前 $i-1$ 个砝码可以称出重量 $j-w_i$，或者前 $i-1$ 个砝码可以称出重量 $j+w_i$。这是一个典型的 01 背包问题，可以使用滚动数组优化空间复杂度。

最终的答案就是 $\sum_{i=1}^{\frac{\sum_{j=1}^N w_j}{2}} f(N,i)$，也就是可以称出的不同的正整数重量的个数。其中 $\frac{\sum_{j=1}^N w_j}{2}$ 是因为天平两侧的重量必须相等。