我们需要按什么顺序在秤上称重？
In what order we need to put weights on scale?
正在做编程作业，不知道如何解决这个问题：
我们有一组 n 个权重，我们将它们一个一个地放在一个秤上，直到使用所有权重。我们还有一串 n 个字母 "R" 或 "L" 表示在那一刻哪支笔更重，它们不能保持平衡。不存在质量相同的砝码。计算我们必须按什么顺序将重量放在秤上以及放在哪个平底锅上。
目标是找到在秤上放置权重的顺序，因此输入字符串得到尊重。
输入：数字 0 < n < 51，权重数。然后是权重和字符串。
输出：在 n 行中，重量和 "R" 或 "L"，放置重量的一侧。如果有很多，输出其中的任何一个。
示例 1：
输入：
3
10 20 30
LRL
输出：
10 L
20 R
30 L
示例 2：
输入：
3
10 20 30
LLR
输出：
20 L
10 R
30 R
示例 3：
输入：
5
10 20 30 40 50
LLLLR
输出：
50 L
10 L
20 R
30 R
40 R
我已经尝试用递归计算它但没有成功。有人可以帮我解决这个问题，或者只是给我提示如何解决它。
既然你没有展示任何自己的代码，那么我将在没有代码的情况下给你一些想法。如果您需要更多帮助，请展示更多您的作品，然后我可以向您展示 Python 解决您问题的代码。
你的问题适合backtracking。维基百科对该算法的定义是
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
和
Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.
您的问题满足这些要求。在每个阶段，您需要选择剩余的重量之一和秤的两个盘子之一。当您将选定的重量放在选定的盘上时，您确定是否满足输入字符串中的相应字母。如果不是，则拒绝选择重量和平底锅。如果是这样，您可以继续选择另一个砝码和平移盘。
您的整个例程首先输入并准备数据。然后它调用一个递归例程，在每个级别选择一个重量和一个平底锅。每个级别所需的一些信息可以放入可变全局变量中，但如果将所有需要的信息作为参数传递会更清楚。每次调用递归例程需要传递：
- 尚未使用的权重
- 输入的L/R字符串尚未使用
- 平底锅上的重量的当前状态，其格式可以在最终确定时轻松打印（可能是重量和平底锅的有序对数组）
- 盘子的当前重量不平衡。这可以从前面的参数计算出来，但是通过单独传递它可以节省时间。这将是右盘上的总重量减去左盘上的总重量（反之亦然）。
递归的基本情况是 unused-weights 和 unused-letters 为空。然后您就完成了搜索并可以打印解决方案并退出程序。否则，您将遍历一个未使用的砝码和一个平底锅的所有组合。对于每个组合，计算如果将那个重量放在那个盘子上，新的不平衡会是多少。如果新的不平衡与相应的字母一致，则使用 appropriately-modified 参数递归调用例程。如果不是，请对此重量和平底锅不做任何操作。
在编码之前你还有一些选择要做，比如未使用权重的数据结构。向我展示一些您自己的编码成果，然后我会给您我的 Python 代码。
请注意，对于大量权重，这可能会很慢。对于 n 个砝码和两个盘子，将砝码放在盘子上的方式总数为 n! * 2**n（即阶乘和求幂）。对于超过 3e79 的 n = 50，太大而无法完成。回溯避免了大多数选择组，因为选择会尽快被拒绝，但我的算法可能仍然很慢。可能有比回溯更好的算法，但我没有看到。你的问题好像是设计来回溯处理的。
既然你已经表现出了更多的努力，这是我的 un-optimized Python 3 代码。这适用于您提供的所有示例，尽管我为您的第三个示例提供了不同的有效解决方案。
def weights_on_pans():
def solve(unused_weights, unused_tilts, placement, imbalance):
"""Place the weights on the scales using recursive
backtracking. Return True if successful, False otherwise."""
if not unused_weights:
# Done: print the placement and note that we succeeded
for weight, pan in placement:
print(weight, 'L' if pan < 0 else 'R')
return True # success right now
tilt, *later_tilts = unused_tilts
for weight in unused_weights:
for pan in (-1, 1): # -1 means left, 1 means right
new_imbalance = imbalance + pan * weight
if new_imbalance * tilt > 0: # both negative or both positive
# Continue searching since imbalance in proper direction
if solve(unused_weights - {weight},
later_tilts,
placement + [(weight, pan)],
new_imbalance):
return True # success at a lower level
return False # not yet successful
# Get the inputs from standard input. (This version has no validity checks)
cnt_weights = int(input())
weights = {int(item) for item in input().split()}
letters = input()
# Call the recursive routine with appropriate starting parameters.
tilts = [(-1 if letter == 'L' else 1) for letter in letters]
solve(weights, tilts, [], 0)
weights_on_pans()
我认为加快该代码的主要方法是避免在内循环中调用 solve 时的 O(n) 操作。这意味着可能改变 unused_weights 的数据结构并改变它的方式，placement，也许 unused_tilts/later_tilts 被修改为使用 O(1) 操作。这些更改会使代码复杂化，这就是我没有这样做的原因。
正在做编程作业，不知道如何解决这个问题：
我们有一组 n 个权重，我们将它们一个一个地放在一个秤上，直到使用所有权重。我们还有一串 n 个字母 "R" 或 "L" 表示在那一刻哪支笔更重，它们不能保持平衡。不存在质量相同的砝码。计算我们必须按什么顺序将重量放在秤上以及放在哪个平底锅上。
目标是找到在秤上放置权重的顺序，因此输入字符串得到尊重。
输入：数字 0 < n < 51，权重数。然后是权重和字符串。
输出：在 n 行中，重量和 "R" 或 "L"，放置重量的一侧。如果有很多，输出其中的任何一个。
示例 1：
输入：
3
10 20 30
LRL
输出：
10 L
20 R
30 L
示例 2：
输入：
3
10 20 30
LLR
输出：
20 L
10 R
30 R
示例 3：
输入：
5
10 20 30 40 50
LLLLR
输出：
50 L
10 L
20 R
30 R
40 R
我已经尝试用递归计算它但没有成功。有人可以帮我解决这个问题，或者只是给我提示如何解决它。
既然你没有展示任何自己的代码，那么我将在没有代码的情况下给你一些想法。如果您需要更多帮助，请展示更多您的作品，然后我可以向您展示 Python 解决您问题的代码。
你的问题适合backtracking。维基百科对该算法的定义是
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
和
Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.
您的问题满足这些要求。在每个阶段，您需要选择剩余的重量之一和秤的两个盘子之一。当您将选定的重量放在选定的盘上时，您确定是否满足输入字符串中的相应字母。如果不是，则拒绝选择重量和平底锅。如果是这样，您可以继续选择另一个砝码和平移盘。
您的整个例程首先输入并准备数据。然后它调用一个递归例程，在每个级别选择一个重量和一个平底锅。每个级别所需的一些信息可以放入可变全局变量中，但如果将所有需要的信息作为参数传递会更清楚。每次调用递归例程需要传递：
- 尚未使用的权重
- 输入的L/R字符串尚未使用
- 平底锅上的重量的当前状态，其格式可以在最终确定时轻松打印（可能是重量和平底锅的有序对数组）
- 盘子的当前重量不平衡。这可以从前面的参数计算出来，但是通过单独传递它可以节省时间。这将是右盘上的总重量减去左盘上的总重量（反之亦然）。
递归的基本情况是 unused-weights 和 unused-letters 为空。然后您就完成了搜索并可以打印解决方案并退出程序。否则，您将遍历一个未使用的砝码和一个平底锅的所有组合。对于每个组合，计算如果将那个重量放在那个盘子上，新的不平衡会是多少。如果新的不平衡与相应的字母一致，则使用 appropriately-modified 参数递归调用例程。如果不是，请对此重量和平底锅不做任何操作。
在编码之前你还有一些选择要做，比如未使用权重的数据结构。向我展示一些您自己的编码成果，然后我会给您我的 Python 代码。
请注意，对于大量权重，这可能会很慢。对于 n 个砝码和两个盘子，将砝码放在盘子上的方式总数为 n! * 2**n（即阶乘和求幂）。对于超过 3e79 的 n = 50，太大而无法完成。回溯避免了大多数选择组，因为选择会尽快被拒绝，但我的算法可能仍然很慢。可能有比回溯更好的算法，但我没有看到。你的问题好像是设计来回溯处理的。
既然你已经表现出了更多的努力，这是我的 un-optimized Python 3 代码。这适用于您提供的所有示例，尽管我为您的第三个示例提供了不同的有效解决方案。
def weights_on_pans():
def solve(unused_weights, unused_tilts, placement, imbalance):
"""Place the weights on the scales using recursive
backtracking. Return True if successful, False otherwise."""
if not unused_weights:
# Done: print the placement and note that we succeeded
for weight, pan in placement:
print(weight, 'L' if pan < 0 else 'R')
return True # success right now
tilt, *later_tilts = unused_tilts
for weight in unused_weights:
for pan in (-1, 1): # -1 means left, 1 means right
new_imbalance = imbalance + pan * weight
if new_imbalance * tilt > 0: # both negative or both positive
# Continue searching since imbalance in proper direction
if solve(unused_weights - {weight},
later_tilts,
placement + [(weight, pan)],
new_imbalance):
return True # success at a lower level
return False # not yet successful
# Get the inputs from standard input. (This version has no validity checks)
cnt_weights = int(input())
weights = {int(item) for item in input().split()}
letters = input()
# Call the recursive routine with appropriate starting parameters.
tilts = [(-1 if letter == 'L' else 1) for letter in letters]
solve(weights, tilts, [], 0)
weights_on_pans()
我认为加快该代码的主要方法是避免在内循环中调用 solve 时的 O(n) 操作。这意味着可能改变 unused_weights 的数据结构并改变它的方式，placement，也许 unused_tilts/later_tilts 被修改为使用 O(1) 操作。这些更改会使代码复杂化，这就是我没有这样做的原因。