Settling Salesman Problem 销售员问题如何实现

Question

Problem Description
After travelling around for years, Salesman John has decided to settle. He wants to build a new house close to his customers, so he doesn't have to travel as much any more. Luckily John knows the location of all of his customers.
All of the customers' locations are at (distinct) integer coordinates. John's new house should also be built on integer coordinates, which cannot be the same as any of the customers' locations. Since John lives in a large and crowded city, the travelling distance to any customer is the Manhattan distance: |x - xi| + |y - yi|, where (x, y) and (xi, yi) are the coordinates of the new house and a customer respectively.
What is the number of locations where John could settle, so the sum of the distance to all of his customers is as low as posible?

Input
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 2 000): the number of customers John has.

n lines with two integers xi and yi (-1 000 000 000 <= xi, yi <= 1 000 000 000): the coordinates of the i-th customer.

Output
For each test case:

Two space-separated integers: the minimum summed distance to all customers, and the number of spots on which John can build his new house to achieve this minimum.

Sample Input
2
4
1 -3
0 1
-2 1
1 -1
2
-999888777 1000000000
1000000000 -987654321

Sample Output
10 4
3987543098 3975087573110998514

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# Import necessary packages
import numpy as np

def manhattan_distance(x1, y1, x2, y2):
    """Calculate the Manhattan distance between two points."""
    return abs(x1 - x2) + abs(y1 - y2)

def solve_salesman(n, customers):
    """Find the minimum sum of distances from all customers to a settlement point."""
    # Initialize the solution array
    solution = [float('inf')] * n
    
    # Calculate the total distance by considering all possible settlements
    for i in range(1 << n):
        total_distance = 0
        for j in range(n):
            if i & (1 << j):
                total_distance += manhattan_distance(customers[j][0], customers[j][1],
                                                    customers[(j+1) % n][0], customers[(j+1) % n][1])
        
        # Update the solution array if a better settlement is found
        if total_distance < solution[0]:
            solution = [total_distance]
    
    # Return the minimum sum of distances and the number of settlements
    return min(solution), len(solution)

# Read input data from stdin
t = int(input())
for _ in range(t):
    n = int(input())
    customers = []
    for _ in range(n):
        x, y = map(int, input().split())
        customers.append((x, y))
    
    # Solve the problem
    result = solve_salesman(n, customers)
    print(result[0], result[1])