On a 2D grid representing a campus, there are n workers and m bikes, with 1 <= n <= m <= 10. Each worker and bike is assigned a 2D coordinate on this grid. The tasks is to assign one unique bike to each worker in a way that minimizes the sum of the Manhattan distances between each worker and their assigned bike. The task is to return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

The Manhattan distance between two points p1 and p2 is calculated as follows: Manhattan(p1, p2) = |p1.x – p2.x| + |p1.y – p2.y|

Example:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Approach: (Top-Down Dynamic Programming + BitMasking)

There are two elements of this problem that serve as hints for another way to approach the problem:

• The problem requires us to minimize the distance sum by making sequential decisions (assigning bikes to workers).
• Each decision we make is affected by the previous decisions we made (which bikes are available depends on which bikes have already been assigned). These are both characteristics of problems that can be solved using dynamic programming. Thus, in this approach, we will use recursive dynamic programming.

In this approach, we will be using bits to represent mark the availability of bikes. Since the maximum number of bikes is less than 32, we can use bitmasking to represent which bikes have been taken with a single integer.

The availability of bikes is now represented by an integer mask having 10 bits. The 10 bits represent the states of 10 bikes. A value of 0 at the ith bit signifies that the bike at the ith index is available while a value of 1 signifies that the bike has been assigned to a worker.

For every worker starting from the worker at index 0, we will traverse over the bikes and assign it to the worker if it is available. Availability of ith bike can be checked by the ith bit in mask, the bike is available if the ith bit in mask is 0. When we assign a bike to the worker we should mark it as unavailable for further workers and for that we need to change the ith bit to 1.

In this approach we need to check/set/unset a particular bit in an integer.

The below slides show how bitwise AND (&) can be used to check if the ith bit is set, how bitwise OR (|) can be used to set the ith bit, and how bitwise XOR (^) can be used to unset the ith bit.

Steps-by-step approach::

• Implement the findDistance() function:
  • This function calculates the Manhattan distance between a worker and a bike.
• Implement the minimumDistanceSum() function:
  • This function recursively finds the minimum total distance for assigning bikes to workers.
  • It iterates through all the available bikes and checks if they are not already assigned (using the mask variable).
  • For each available bike, it calculates the distance between the current worker and the bike, and then recursively calls the function for the next worker with the updated mask.
  • The function keeps track of the smallest total distance found so far and returns it.
  • If the result for the current mask is already calculated, the function returns the stored value from the memo array.
• Implement the assignBikes() function:
  • This function is the main entry point of the solution.
  • It initializes the memo array to -1 to indicate that the results have not been calculated yet.
  • It then calls the minimumDistanceSum function with the initial worker index 0 and an initial mask of 0 (no bikes assigned yet).
  • Returns the minimum total distance for assigning bikes to all workers.

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;

// Maximum value of mask will be 2^(Number of bikes)
// and number of bikes can be 10 at max
int memo[1024];

// Manhattan distance
int findDistance(vector<int>& worker, vector<int>& bike)
{
    return abs(worker[0] - bike[0])
           + abs(worker[1] - bike[1]);
}

// Function to find minimum distance sum for assigning bikes
// to workers
int minimumDistanceSum(vector<vector<int> >& workers,
                       vector<vector<int> >& bikes,
                       int workerIndex, int mask)
{
    if (workerIndex >= workers.size()) {
        return 0; // No more workers, return 0 distance
    }

    // If result is already calculated, return it no
    // recursion needed
    if (memo[mask] != -1)
        return memo[mask];

    int smallestDistanceSum = INT_MAX;
    for (int bikeIndex = 0; bikeIndex < bikes.size();
         bikeIndex++) {
        // Check if the bike at bikeIndex is available (not
        // assigned yet)
        if ((mask & (1 << bikeIndex)) == 0) {
            // Add current distance and find distance for
            // next worker with updated mask
            smallestDistanceSum = min(
                smallestDistanceSum,
                findDistance(workers[workerIndex],
                             bikes[bikeIndex])
                    + minimumDistanceSum(
                        workers, bikes, workerIndex + 1,
                        mask | (1 << bikeIndex)));
        }
    }

    // Memoizing the result corresponding to mask
    return memo[mask] = smallestDistanceSum;
}

int assignBikes(vector<vector<int> >& workers,
                vector<vector<int> >& bikes)
{
    // Marking all positions to -1 that signifies result
    // has not been calculated yet for this mask
    memset(memo, -1, sizeof(memo));
    return minimumDistanceSum(workers, bikes, 0, 0);
}

int main()
{
    // Sample input
    vector<vector<int> > workers = { { 0, 0 }, { 2, 1 } };
    vector<vector<int> > bikes = { { 1, 2 }, { 3, 3 } };

    int minimumDistance = assignBikes(workers, bikes);
    cout << "Minimum distance sum for assigning bikes: "
         << minimumDistance << endl;

    return 0;
}

import java.util.*;

public class Main {

    // Maximum value of mask will be 2^(Number of bikes)
    // and number of bikes can be 10 at max
    static int[] memo;

    // Manhattan distance
    public static int findDistance(int[] worker, int[] bike)
    {
        return Math.abs(worker[0] - bike[0])
            + Math.abs(worker[1] - bike[1]);
    }

    // Function to find minimum distance sum for assigning
    // bikes to workers
    public static int minimumDistanceSum(int[][] workers,
                                         int[][] bikes,
                                         int workerIndex,
                                         int mask)
    {
        if (workerIndex >= workers.length) {
            return 0; // No more workers, return 0 distance
        }

        // If result is already calculated, return it, no
        // recursion needed
        if (memo[mask] != -1)
            return memo[mask];

        int smallestDistanceSum = Integer.MAX_VALUE;
        for (int bikeIndex = 0; bikeIndex < bikes.length;
             bikeIndex++) {
            // Check if the bike at bikeIndex is available
            // (not assigned yet)
            if ((mask & (1 << bikeIndex)) == 0) {
                // Add current distance and find distance
                // for next worker with updated mask
                smallestDistanceSum = Math.min(
                    smallestDistanceSum,
                    findDistance(workers[workerIndex],
                                 bikes[bikeIndex])
                        + minimumDistanceSum(
                            workers, bikes, workerIndex + 1,
                            mask | (1 << bikeIndex)));
            }
        }

        // Memoizing the result corresponding to mask
        return memo[mask] = smallestDistanceSum;
    }

    public static int assignBikes(int[][] workers,
                                  int[][] bikes)
    {
        // Marking all positions to -1 that signifies result
        // has not been calculated yet for this mask
        memo = new int[1024];
        Arrays.fill(memo, -1);
        return minimumDistanceSum(workers, bikes, 0, 0);
    }

    public static void main(String[] args)
    {
        // Sample input
        int[][] workers = { { 0, 0 }, { 2, 1 } };
        int[][] bikes = { { 1, 2 }, { 3, 3 } };

        int minimumDistance = assignBikes(workers, bikes);
        System.out.println(
            "Minimum distance sum for assigning bikes: "
            + minimumDistance);
    }
}

// This code is contributed by Shivam Gupta

from typing import List

# Function to calculate the Manhattan distance between a worker and a bike


def find_distance(worker: List[int], bike: List[int]) -> int:
    return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])


def minimum_distance_sum(workers: List[List[int]], bikes: List[List[int]], worker_index: int, mask: int, memo: List[int]) -> int:
    # Base case: if all workers have been assigned bikes
    if worker_index >= len(workers):
        return 0
    if memo[mask] != -1:
        return memo[mask]
    smallest_distance_sum = float('inf')  # Initialize to a very large number
    # Try assigning each bike to the current worker
    for bike_index in range(len(bikes)):
        if (mask & (1 << bike_index)) == 0:
            distance_sum = find_distance(workers[worker_index], bikes[bike_index]) + \
                minimum_distance_sum(
                    workers, bikes, worker_index + 1, mask | (1 << bike_index), memo)
            # Update the smallest distance sum if the current assignment is better
            smallest_distance_sum = min(smallest_distance_sum, distance_sum)
    # Memoize the result corresponding to the current mask
    memo[mask] = smallest_distance_sum
    return smallest_distance_sum
# Function to assign bikes to the workers minimizing the total distance


def assign_bikes(workers: List[List[int]], bikes: List[List[int]]) -> int:
    max_mask = 1 << len(bikes)
    memo = [-1] * max_mask
    return minimum_distance_sum(workers, bikes, 0, 0, memo)


# Example usage
if __name__ == "__main__":
    # Sample input
    workers = [[0, 0], [2, 1]]
    bikes = [[1, 2], [3, 3]]
    # Calculate the minimum distance sum for the assigning bikes
    minimum_distance = assign_bikes(workers, bikes)
    print("Minimum distance sum for assigning bikes:", minimum_distance)

const memo = new Array(1024).fill(-1);

// Manhattan distance
function findDistance(worker, bike) {
    return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
}

// Function to find minimum distance sum for assigning bikes to workers
function minimumDistanceSum(workers, bikes, workerIndex, mask) {
    if (workerIndex >= workers.length) {
        return 0; // No more workers, return 0 distance
    }

    // If result is already calculated, return it no recursion needed
    if (memo[mask] !== -1) {
        return memo[mask];
    }

    let smallestDistanceSum = Number.MAX_SAFE_INTEGER;
    for (let bikeIndex = 0; bikeIndex < bikes.length; bikeIndex++) {
        // Check if the bike at bikeIndex is available (not assigned yet)
        if ((mask & (1 << bikeIndex)) === 0) {
            // Add current distance and find distance for next worker with updated mask
            smallestDistanceSum = Math.min(
                smallestDistanceSum,
                findDistance(workers[workerIndex], bikes[bikeIndex]) +
                minimumDistanceSum(workers, bikes, workerIndex + 1, mask | (1 << bikeIndex))
            );
        }
    }

    // Memoizing the result corresponding to mask
    return memo[mask] = smallestDistanceSum;
}

function assignBikes(workers, bikes) {
    // Marking all positions to -1 that signifies result has not been calculated yet for this mask
    memo.fill(-1);
    return minimumDistanceSum(workers, bikes, 0, 0);
}

// Sample input
const workers = [[0, 0], [2, 1]];
const bikes = [[1, 2], [3, 3]];

const minimumDistance = assignBikes(workers, bikes);
console.log("Minimum distance sum for assigning bikes: " + minimumDistance);

// This code is contributed by Ayush Mishra

Minimum distance sum for assigning bikes: 6

Time complexity: O(M* 2^M), Here N is the number of workers, and M is the number of bikes.
Auxiliary Space: O(2^ M)

Related Article:

• Assign Campus Bikes to Workers