你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN 。 请你计算一共可以称出多少种不同的正整数重量? 注意砝码可以放在天平两边。
时间: 2023-05-31 18:06:27 浏览: 76
假设天平左边的砝码重量总和为 $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}$ 是因为天平两侧的重量必须相等。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)