作业-人员分配的最小最大成本多项式时间算法设计问询

Hey there! Let's start by breaking down what's not working with your current function, then walk through the correct polynomial-time approach to solve this "minimize the maximum cost" assignment problem.

We need to assign every job to exactly one person (people can handle multiple jobs unless specified otherwise), and our goal is to minimize the largest cost among all assigned person-job pairs—this is very different from minimizing total cost, which is a common pitfall!

First, let's restate your function clearly in code blocks for clarity:

Function MinimumCost
Pass in: array of jobs as jobArr, array of people as peopleArr
m <-- length(jobArr)
n <-- length(peopleArr)
call <-- sort(jobArr)
call <-- sort(peopleArr)
assignment  array of pairs for person-job pairs
i <-- 0
j <-- m-1
While j >= 0
    IF i == n Then
        i <-- 0
    EndIF
    assignment[i]  pair of peopleArr[i] and jobArr[j]
    j <-- j – 1
    i <-- i – 1
End While
End Function

Here are the critical flaws:

• No consideration of person-job costs: You're sorting jobs and people in isolation, but the cost is a property of the pair, not the individual job or person. This means your assignment has no connection to the actual cost values we care about—this will almost always produce a suboptimal or outright wrong result.
• Broken indexing logic: Your i variable decrements each iteration, which will quickly lead to negative indices (e.g., starting with i=0, after one step i=-1). This will cause array out-of-bounds errors and invalid assignments.
• No handling of feasibility: You don't check if a person can even perform a job (based on cost) before assigning it—you're just pairing sorted lists blindly.

Let's say we have:

• peopleArr = [Alice, Bob, Charlie]
• Cost matrix (person → job cost):
  • Alice: Job A=3, Job B=1, Job C=5
  • Bob: Job A=4, Job B=6, Job C=2
  • Charlie: Job A=7, Job B=8, Job C=9
• jobArr = [Job A, Job B, Job C]

The optimal assignment to minimize maximum cost is:

• Charlie → Job A (cost 7), Alice → Job B (cost 1), Bob → Job C (cost 2)
• Maximum cost here is 7.

Your function would sort the people and jobs, then assign Charlie→Job C (cost 9), Bob→Job B (cost 6), Alice→Job A (cost3)—resulting in a maximum cost of 9, which is worse than the optimal 7.

This is a classic min-max optimization problem, which we can solve efficiently with binary search + feasibility checking:

Step 1: Frame the Problem for Binary Search #

We're looking for the smallest value X such that we can assign every job to a person where the cost of that pair is ≤ X.

• Initialize low to the smallest cost in the entire cost matrix, high to the largest cost.
• Use binary search to narrow down the smallest feasible X.

Step 2: Feasibility Check #

The feasibility check depends on whether people can handle multiple jobs or not:

Case 1: People can handle multiple jobs #

We just need to confirm that every job has at least one person who can do it for cost ≤ X. This is O(m*n) time, where m = number of jobs, n = number of people.

Case 2: Each person can handle at most one job (1:1 assignment, n=m) #

We need to check if there's a perfect matching in a bipartite graph where edges exist between people and jobs if their cost is ≤ X. We can use the Hungarian algorithm for this (O(n³) time, which is polynomial).

Step 3: Construct the Assignment #

Once we find the smallest feasible X, we can go back and assign each job to any person who can do it for ≤ X (or find the perfect matching for 1:1 cases).

Example Pseudo-Code (People can handle multiple jobs) #

Function MinimumMaxCost
Pass in: jobArr, peopleArr, costMatrix (cost[i][j] = cost of person i doing job j)
m = length(jobArr)
n = length(peopleArr)

// Set initial binary search bounds
low = Infinity
high = 0
for i from 0 to n-1:
    for j from 0 to m-1:
        low = min(low, costMatrix[i][j])
        high = max(high, costMatrix[i][j])

min_max_cost = high

// Binary search for the smallest feasible X
while low <= high:
    mid = (low + high) // 2
    feasible = true
    
    // Check if every job has at least one person who can do it for ≤ mid
    for j from 0 to m-1:
        has_valid_person = false
        for i from 0 to n-1:
            if costMatrix[i][j] <= mid:
                has_valid_person = true
                break
        if not has_valid_person:
            feasible = false
            break
    
    if feasible:
        min_max_cost = mid
        high = mid - 1  // Try to find a smaller feasible X
    else:
        low = mid + 1   // Need a larger X

// Build the assignment
assignment = []
for j from 0 to m-1:
    // Find the first person who can do job j for ≤ min_max_cost
    for i from 0 to n-1:
        if costMatrix[i][j] <= min_max_cost:
            assignment.append( (peopleArr[i], jobArr[j]) )
            break

return assignment, min_max_cost
End Function

Example Pseudo-Code for 1:1 Assignment (Hungarian Algorithm for Feasibility) #

If you need 1:1 assignments (each person does exactly one job), here's how to adjust the feasibility check:

Function HasPerfectMatch(mid, costMatrix, n):
    // matchTo[j] = person assigned to job j
    matchTo = [-1] * n
    result = 0
    
    for person in 0 to n-1:
        visited = [false] * n
        if DFS(person, mid, costMatrix, matchTo, visited):
            result += 1
    return result == n

// Helper DFS for bipartite matching
Function DFS(person, mid, costMatrix, matchTo, visited):
    for job in 0 to n-1:
        if costMatrix[person][job] <= mid and not visited[job]:
            visited[job] = true
            if matchTo[job] == -1 or DFS(matchTo[job], mid, costMatrix, matchTo, visited):
                matchTo[job] = person
                return true
    return false

This approach runs in polynomial time:

• For multi-job per person: O(mnlog(max_cost))
• For 1:1 assignments: O(n³*log(max_cost))

Both are well within the polynomial time requirement, and they correctly target the goal of minimizing the maximum assignment cost.

内容的提问来源于stack exchange，提问作者M.Ayoub