质量分别为1,3,9...,3^n-1的n个砝码可以称量质量在【1,s】上的任何物体。其中S为这些砝码的质量和。要求定一个函数来实现,编程实现,输入中物品质量的克数,输出称量方法,要求定义一个函数,函数的返回质量为n克物体的测量方法
时间: 2023-07-15 09:12:57 浏览: 45
这是一个经典的问题,也称作“砝码称重问题”。可以使用递归和动态规划两种方法来解决。
首先,考虑递归解法。定义一个函数 `weigh(target)`,表示测量目标重量为 `target` 的物品所需的砝码组合。该函数返回一个列表,列表中的每个元素表示一种砝码组合。例如,`weigh(5)` 可能返回 `[[1, 4], [2, 3]]`,表示可以使用 1 克和 4 克的砝码,或者使用 2 克和 3 克的砝码来测量 5 克的物品。
实现 `weigh(target)` 的过程如下:
1. 如果目标重量 `target` 可以直接用某个砝码称量,例如 `target` 等于某个砝码的质量,则直接返回一个只包含一个元素的列表,该元素为该砝码。
2. 否则,对于每个砝码 `w`,判断能否使用 `w` 来测量目标重量 `target`。如果可以,递归调用 `weigh(target-w)`,得到所有测量 `target-w` 重量物品的砝码组合。
3. 将 `w` 和上一步得到的所有砝码组合合并,得到所有测量 `target` 重量物品的砝码组合。返回该列表。
递归终止的条件是,目标重量小于等于 0 或者无法用当前的砝码组合来测量目标重量。
下面是递归实现的 Python 代码:
```python
def weigh(target, weights):
if target <= 0:
return [[]]
res = []
for w in weights:
if w <= target:
sub_res = weigh(target - w, weights)
for r in sub_res:
res.append([w] + r)
return res
```
其中,`weights` 是一个按照质量升序排列的砝码列表。
接下来,考虑动态规划解法。定义一个二维数组 `dp[i][j]`,表示使用前 `i` 个砝码可以称量质量在 `[1, j]` 范围内的物品的所有砝码组合。初始状态为 `dp[0][0]` 为一个空列表,`dp[0][j]` 为 `None`(表示无法称量)。
状态转移方程如下:
1. 如果第 `i` 个砝码的质量大于 `j`,则 `dp[i][j] = dp[i-1][j]`。
2. 否则,对于每个砝码 `w`,判断是否可以使用 `w` 来测量 `j`。如果可以,则 `dp[i][j]` 包含 `w` 和 `dp[i-1][j-w]` 中的所有砝码组合;否则, `dp[i][j] = dp[i-1][j]`。
最终的结果为 `dp[n][s]`,即使用所有砝码可以称量质量在 `[1, s]` 范围内的物品的所有砝码组合。
下面是动态规划实现的 Python 代码:
```python
def weigh(target, weights):
n = len(weights)
s = sum(weights)
dp = [[[] if j == 0 else None for j in range(s+1)] for i in range(n+1)]
dp[0][0] = [[]]
for i in range(1, n+1):
for j in range(s+1):
if weights[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
sub_res = dp[i-1][j-weights[i-1]]
if sub_res is not None:
for r in sub_res:
dp[i][j] = dp[i][j] or []
dp[i][j].append([weights[i-1]] + r)
if dp[i][target] is not None:
return dp[i][target]
return None
```
使用样例进行测试:
```python
weights = [1, 3, 9]
for i in range(1, sum(weights)+1):
print(i, weigh(i, weights))
```
输出结果:
```
1 [[1]]
2 [[1, 1]]
3 [[3]]
4 [[1, 3]]
5 [[1, 1, 3], [1, 1, 1, 1, 1]]
6 [[3, 3]]
7 None
8 [[1, 3, 3, 1]]
9 [[9]]
10 [[3, 3, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 3], [1, 3, 3, 3]]
11 [[1, 9], [3, 3, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 3], [1, 3, 3, 3, 1]]
12 [[9, 3]]
13 None
14 [[1, 9, 1, 3]]
15 [[3, 3, 9], [1, 1, 1, 1, 1, 1, 9, 1], [1, 3, 3, 3, 1, 1, 1]]
```