给定一个列表列表和第二个列表，如何找到可以放入第二个列表的最大列表数？

Question

努力找出如何最有效地解决问题。

给定一个列表列表，例如 [[4, 4], [4, 5, 6], [8, 9, 1]]，和第二个列表，例如 [8, 9, 7, 1]，如何您以编程方式（Python）找到第一个列表中可以从第二个列表中减去的最大列表数？列表的顺序必须保持不变。因此，使用示例，最大值将为 2，因为：

[4, 4] 进入第二个列表的第一个和第二个元素 -> [4, 5, 7, 1] [4, 5, 6] 进入上面结果列表的第一个、第二个和第三个元素 -> [0, 0, 1, 1]

如果我们尝试将 [8, 9, 1] 放入 [8, 9, 7, 1]，我们会得到 [0, 0, 6, 1] 余数，而不会得到 [4, 4] 和 [4] , 5, 6] 可以适合这个。

我希望这是有道理的！我一直在努力用语言表达它。

谢谢

Answer 1

我会用 我们的问题可以使用回溯算法来解决。您可以尝试第一个列表中的每个列表，从第二个列表中减去它（如果可能），然后递归地尝试将第一个列表中的下一个列表放入第二个列表的其余部分。目标是找到可以通过这种方式减去的列表的最大数量。

我会像下面这样处理它：

def can_subtract(list1, list2):
    """
    Try to subtract list1 from list2 starting from any position.
    Returns the resulting list if possible, otherwise None.
    """
    n, m = len(list1), len(list2)
    for i in range(m - n + 1):  # Try all starting positions in list2
        if all(list2[i+j] >= list1[j] for j in range(n)):
            # Subtract list1 from list2 starting from index i
            new_list2 = list2[:]
            for j in range(n):
                new_list2[i+j] -= list1[j]
            return new_list2
    return None

def max_lists_subtracted(lists, target_list):
    def backtrack(index, current_list, count):
        nonlocal max_count
        if index >= len(lists):
            max_count = max(max_count, count)
            return
        
        # Try to subtract the current list
        result = can_subtract(lists[index], current_list)
        if result is not None:
            # If successful, move to the next list
            backtrack(index + 1, result, count + 1)
        
        # Also consider not using the current list and moving to the next
        backtrack(index + 1, current_list, count)
    
    max_count = 0
    backtrack(0, target_list, 0)
    return max_count

# Example usage:
lists = [[4, 4], [4, 5, 6], [8, 9, 1]]
target_list = [8, 9, 7, 1]
print(max_lists_subtracted(lists, target_list))  # Output is 2 

所以，这里

1. can_subtract(list1, list2)

   ：检查是否可以从任意位置开始从

   list1

   中减去

   list2

   。如果可能的话，返回减法后修改后的

   list2

   ；否则，返回

   None

   。
2. 其次，

   max_lists_subtracted(lists, target_list)

   使用回溯来尝试从

   target_list

   中减去列表中的每个列表。它跟踪可以减去的列表的最大数量。