爱做实验的平平经常使用天平称量重物,有一天他发现,在天平右边托盘中放置了 ww 克的重物时,在左边托盘中用好几种不同的砝码放置方案都可以让天平进入平衡状态。他很想知道,用手头 nn 个不同重量的砝码,究竟有多少种不同的放置方案能与这个 ww 克的重物平衡。 你能否编一个代码帮他解决这个问题?由于答案可能很大,所以只需输出方案总数除以 201809201809 的余数。
时间: 2024-02-11 17:07:46 浏览: 181
天平称重,砝码组合
好的,这是一个比较典型的背包问题。我们可以使用动态规划的思想来解决。设 $f(i,j)$ 表示使用前 $i$ 个砝码,能否凑出重量为 $j$。则有转移方程:
$$
f(i,j) = f(i-1,j-w_i) \lor f(i-1,j)
$$
其中 $\lor$ 表示逻辑或操作,即两个值中有一个为真,结果就为真。边界条件为 $f(0,0)=1$,其余均为 $0$。最终答案即为 $\sum_{j=0}^{w}f(n,j)$,其中 $w$ 是重物的重量,$n$ 是砝码的个数。最后再对答案取模即可。
下面是对应的 Python 代码实现:
```python
w, n = map(int, input().split())
weights = list(map(int, input().split()))
MOD = 201809201809
f = [[0] * (w + 1) for _ in range(n + 1)]
f[0][0] = 1
for i in range(1, n + 1):
for j in range(w + 1):
f[i][j] = f[i-1][j]
if j >= weights[i-1]:
f[i][j] |= f[i-1][j-weights[i-1]]
ans = sum(f[n]) % MOD
print(ans)
```
注意,这里的第二行输入了重量和砝码个数,接下来的一行输入了每个砝码的重量。
阅读全文