Minimizing Total Manhattan Distances for Driver-Package Allocation
Given two integers n and m, where n represents delivery drivers and m represents the number of packages, Additionally, their position are also given in drivers[][] and packages[][] respectively. The task is to allocate each driver a unique package such that the sum of total Manhattan distances between the drivers and their respective packages are minimized.
Constraints: 1 <= n <= m <= 10
Example:
Input: drivers = {{0,0},{2,1}}, packages = {{1,2},{3,3}}
Output: 6
Explanation: Allocate package 0 to driver 0, and package 1 to driver 1. The Manhattan distance of both allotments is 3, so the output is 6.Input: arr1 = {{0,0},{1,1},{2,0}}, arr2 = {{1,0},{2,2},{2,1}}
Output: 4
Approach:
This approach uses a technique called bitmasking to keep track of which packages have been assigned to drivers. Bitmasking is a way to use bits to represent a set of items. In this case, each bit in an integer represents a package.
Imagine you have a row of light bulbs (packages) that can be either on (assigned) or off (available). This row of light bulbs is represented by an integer, where each bit in the integer is a light bulb. A bit value of 0 means the light bulb is off (the package is available), and a bit value of 1 means the light bulb is on (the package is assigned).
Now, for each driver, starting from the first one, we go through the packages and assign an available package to the driver. We can check if a package is available by looking at the corresponding bit in our integer. If the bit is 0, the package is available.
When we assign a package to a driver, we need to mark it as unavailable for the other drivers. We do this by changing the corresponding bit in our integer from 0 to 1.
In this approach, we use bitwise operations to check, set, and unset bits in our integer. Here’s how:
- Bitwise AND (&): We can use this operation to check if a bit is set (1). If the result of bitmask & (1 << i) is not 0, then the ith bit is set.
- Bitwise OR (|): We can use this operation to set a bit (make it 1). The expression bitmask | (1 << i) will set the ith bit.
- Bitwise XOR (^): We can use this operation to unset a bit (make it 0). The expression bitmask ^ (1 << i) will unset the ith bit if it is set.
Steps-by-step approach:
- Create an array memo[] of size 1024 to store the results of subproblems to avoid redundant calculations.
- If all drivers have been assigned a package, returns 0.
- If the result for the current mask has been calculated, it returns the stored result.
- For each available package, calculates the total distance and keeps track of the smallest total distance.
- Update the mask to indicate that the current package has been assigned and recursively calls itself for the next driver.
- The smallest total distance is stored in the memo[] array and returned.
Below is the implementation of the above approach:
#include <climits> // Include for INT_MAX
#include <cstring> // Include for memset
#include <iostream>
#include <vector>
using namespace std;
int memo[1024];
int findDistance(vector<int>& worker, vector<int>& package)
{
return abs(worker[0] - package[0])
+ abs(worker[1] - package[1]);
}
int minimumDistanceSum(vector<vector<int> >& drivers,
vector<vector<int> >& packages,
int driverIdx, int mask)
{
if (driverIdx >= drivers.size()) {
return 0;
}
if (memo[mask] != -1)
return memo[mask];
int smallestDistanceSum = INT_MAX;
for (int packageIdx = 0; packageIdx < packages.size();
packageIdx++) {
if ((mask & (1 << packageIdx)) == 0) {
smallestDistanceSum = min(
smallestDistanceSum,
findDistance(drivers[driverIdx],
packages[packageIdx])
+ minimumDistanceSum(
drivers, packages, driverIdx + 1,
mask | (1 << packageIdx)));
}
}
return memo[mask] = smallestDistanceSum;
}
int assignPackages(vector<vector<int> >& drivers,
vector<vector<int> >& packages)
{
memset(memo, -1, sizeof(memo));
return minimumDistanceSum(drivers, packages, 0, 0);
}
int main()
{
vector<vector<int> > drivers = { { 0, 0 }, { 2, 1 } };
vector<vector<int> > packages = { { 1, 2 }, { 3, 3 } };
cout << assignPackages(drivers, packages) << endl;
return 0;
}
import java.util.Arrays;
import java.util.Vector;
public class PackageAssignment {
static int[] memo = new int[1024];
static int findDistance(Vector<Integer> worker,
Vector<Integer> packageCoord)
{
return Math.abs(worker.get(0) - packageCoord.get(0))
+ Math.abs(worker.get(1) - packageCoord.get(1));
}
static int
minimumDistanceSum(Vector<Vector<Integer> > drivers,
Vector<Vector<Integer> > packages,
int driverIdx, int mask)
{
if (driverIdx >= drivers.size()) {
return 0;
}
if (memo[mask] != -1)
return memo[mask];
int smallestDistanceSum = Integer.MAX_VALUE;
for (int packageIdx = 0;
packageIdx < packages.size(); packageIdx++) {
if ((mask & (1 << packageIdx)) == 0) {
smallestDistanceSum = Math.min(
smallestDistanceSum,
findDistance(drivers.get(driverIdx),
packages.get(packageIdx))
+ minimumDistanceSum(
drivers, packages,
driverIdx + 1,
mask | (1 << packageIdx)));
}
}
return memo[mask] = smallestDistanceSum;
}
static int
assignPackages(Vector<Vector<Integer> > drivers,
Vector<Vector<Integer> > packages)
{
Arrays.fill(memo, -1);
return minimumDistanceSum(drivers, packages, 0, 0);
}
public static void main(String[] args)
{
Vector<Vector<Integer> > drivers = new Vector<>();
drivers.add(new Vector<>(Arrays.asList(0, 0)));
drivers.add(new Vector<>(Arrays.asList(2, 1)));
Vector<Vector<Integer> > packages = new Vector<>();
packages.add(new Vector<>(Arrays.asList(1, 2)));
packages.add(new Vector<>(Arrays.asList(3, 3)));
System.out.println(
assignPackages(drivers, packages));
}
}
def find_distance(worker, package):
# Calculate Manhattan distance
return abs(worker[0] - package[0]) + abs(worker[1] - package[1])
def minimum_distance_sum(drivers, packages, driver_idx, mask, memo):
# Base case: all drivers are assigned
if driver_idx >= len(drivers):
return 0
# If the result for this combination of drivers and packages has already
# been calculated, return it
if memo[mask] != -1:
return memo[mask]
smallest_distance_sum = float('inf')
# Try assigning each package to the current driver
for package_idx in range(len(packages)):
# If the package at package_idx is available (not yet assigned)
if (mask & (1 << package_idx)) == 0:
# Calculate the distance for assigning the package to the current driver
distance = find_distance(
drivers[driver_idx], packages[package_idx])
# Recursively find the minimum distance sum for the remaining drivers
# Update the mask to mark the package as assigned
next_mask = mask | (1 << package_idx)
distance_sum = distance + \
minimum_distance_sum(
drivers, packages, driver_idx + 1, next_mask, memo)
# Update the smallest distance sum found so far
smallest_distance_sum = min(smallest_distance_sum, distance_sum)
# Memoize the result for this combination of drivers and packages
memo[mask] = smallest_distance_sum
return memo[mask]
def assign_packages(drivers, packages):
# Initialize memoization array to store calculated results for each
# combination of assigned packages
memo = [-1] * (1 << len(packages))
# Start the recursive function to assign packages to drivers and minimize the distance sum
return minimum_distance_sum(drivers, packages, 0, 0, memo)
if __name__ == "__main__":
# Sample data
drivers = [[0, 0], [2, 1]]
packages = [[1, 2], [3, 3]]
# Assign packages to drivers and print the minimum distance sum
print(assign_packages(drivers, packages))
# This code is contributed by Susobhan Akhuli
using System;
using System.Collections.Generic;
class GFG {
// Maximum value of mask will be 2^(Number of packages)
// and the number of packages can be 10 at max
static int[] memo = new int[1024];
// Manhattan distance
static int FindDistance(List<int> worker,
List<int> package)
{
return Math.Abs(worker[0] - package[0])
+ Math.Abs(worker[1] - package[1]);
}
static int MinimumDistanceSum(List<List<int> > drivers,
List<List<int> > packages,
int driverIdx, int mask)
{
if (driverIdx >= drivers.Count) {
return 0;
}
// If the result is already calculated, return it;
// no recursion needed
if (memo[mask] != -1)
return memo[mask];
int smallestDistanceSum = int.MaxValue;
for (int packageIdx = 0;
packageIdx < packages.Count; packageIdx++) {
// Check if the package at packageIdx is
// available
if ((mask & (1 << packageIdx)) == 0) {
// Adding the current distance and repeat
// the process for the next worker Also
// changing the bit at index packageIdx to 1
// to show the package is assigned
smallestDistanceSum = Math.Min(
smallestDistanceSum,
FindDistance(drivers[driverIdx],
packages[packageIdx])
+ MinimumDistanceSum(
drivers, packages,
driverIdx + 1,
mask | (1 << packageIdx)));
}
}
// Memoizing the result corresponding to mask
return memo[mask] = smallestDistanceSum;
}
static int AssignPackages(List<List<int> > drivers,
List<List<int> > packages)
{
// Marking all positions to -1 that signifies the
// result has not been calculated yet for this mask
Array.Fill(memo, -1);
return MinimumDistanceSum(drivers, packages, 0, 0);
}
static void Main()
{
List<List<int> > drivers
= new List<List<int> >{ new List<int>{ 0, 0 },
new List<int>{ 2, 1 } };
List<List<int> > packages
= new List<List<int> >{ new List<int>{ 1, 2 },
new List<int>{ 3, 3 } };
Console.WriteLine(
AssignPackages(drivers, packages));
}
}
// Maximum value of mask will be 2^(Number of packages)
// and number of packages can be 10 at max
const memo = new Array(1024).fill(-1);
// Manhattan distance
function findDistance(worker, packageCoord) {
return Math.abs(worker[0] - packageCoord[0]) +
Math.abs(worker[1] - packageCoord[1]);
}
function minimumDistanceSum(drivers, packages, driverIdx, mask) {
if (driverIdx >= drivers.length) {
return 0;
}
// If result is already calculated, return it
// no recursion needed
if (memo[mask] !== -1)
return memo[mask];
let smallestDistanceSum = Number.MAX_VALUE;
for (let packageIdx = 0; packageIdx < packages.length; packageIdx++) {
// Check if the package at packageIdx is available
if ((mask & (1 << packageIdx)) === 0) {
// Adding the current distance and repeat the
// process for next worker also changing the bit
// at index packageIdx to 1 to show the package
// there is assigned
smallestDistanceSum = Math.min(
smallestDistanceSum,
findDistance(drivers[driverIdx], packages[packageIdx]) +
minimumDistanceSum(drivers, packages, driverIdx + 1,
mask | (1 << packageIdx))
);
}
}
// Memoizing the result corresponding to mask
return memo[mask] = smallestDistanceSum;
}
function assignPackages(drivers, packages) {
// Marking all positions to -1 that signifies result
// has not been calculated yet for this mask
memo.fill(-1);
return minimumDistanceSum(drivers, packages, 0, 0);
}
// Driver code
const drivers = [
[0, 0],
[2, 1]
];
const packages = [
[1, 2],
[3, 3]
];
console.log(assignPackages(drivers, packages));
Output
6
Time Complexity: O(2^n * n^2), where n is the maximum number of packages (10 in this case).
Auxiliary space: O(2^n), where n is the maximum number of packages (10 in this case).
Approach: Dynamic Programming with Hungarian Algorithm
To address the task of minimizing the total Manhattan distances in the assignment of drivers to packages more efficiently than the brute-force bitmask approach, we can leverage the Hungarian Algorithm (or Munkres-Kuhn algorithm). This algorithm is specifically designed for solving assignment problems optimally in polynomial time, making it suitable for this scenario where we need to assign n drivers to m packages with the least possible cost.
Steps:
- Cost Matrix Construction: Construct a matrix where each cell [i][j] represents the Manhattan distance between driver i and package j.
- Apply Hungarian Algorithm: Utilize the Hungarian algorithm to find the minimum cost matching.
- Extract the Result: The output from the algorithm provides the optimal assignment to minimize the total Manhattan distance.
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int manhattanDistance(vector<int>& point1,
vector<int>& point2)
{
return abs(point1[0] - point2[0])
+ abs(point1[1] - point2[1]);
}
int assignPackages(vector<vector<int> >& drivers,
vector<vector<int> >& packages)
{
int n = drivers.size();
int m = packages.size();
vector<vector<int> > costMatrix(n, vector<int>(m));
// Create the cost matrix for each driver-package pair
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
costMatrix[i][j] = manhattanDistance(
drivers[i], packages[j]);
}
}
// Apply the Hungarian algorithm to find the minimum
// cost assignment
vector<int> rowInd(n, -1);
vector<int> colInd(m, -1);
vector<bool> assigned(m, false);
for (int k = 0; k < n; k++) {
int minDist = INT_MAX;
int minIndex = -1;
for (int i = 0; i < n; i++) {
if (rowInd[i] != -1)
continue;
for (int j = 0; j < m; j++) {
if (assigned[j])
continue;
if (costMatrix[i][j] < minDist) {
minDist = costMatrix[i][j];
minIndex = j;
}
}
}
rowInd[k] = minIndex;
colInd[minIndex] = k;
assigned[minIndex] = true;
}
// Calculate the total minimum distance by summing the
// assigned costs
int minTotalDistance = 0;
for (int i = 0; i < n; i++) {
minTotalDistance += costMatrix[i][rowInd[i]];
}
return minTotalDistance;
}
int main()
{
vector<vector<int> > drivers = { { 0, 0 }, { 2, 1 } };
vector<vector<int> > packages = { { 1, 2 }, { 3, 3 } };
cout << assignPackages(drivers, packages) << endl;
return 0;
}
import java.util.Arrays;
public class AssignPackages {
// Function to the calculate the Manhattan distance
// between the two points
public static int manhattanDistance(int[] point1,
int[] point2)
{
return Math.abs(point1[0] - point2[0])
+ Math.abs(point1[1] - point2[1]);
}
// Function to assign packages to the drivers and
// minimize total distance
public static int assignPackages(int[][] drivers,
int[][] packages)
{
// Number of the drivers and packages
int n = drivers.length;
int m = packages.length;
// Create the cost matrix for each driver-package
// pair
int[][] costMatrix = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
costMatrix[i][j] = manhattanDistance(
drivers[i], packages[j]);
}
}
// Apply the Hungarian algorithm to the find the
// minimum cost assignment
int[] rowInd = new int[n];
int[] colInd = new int[m];
boolean[] assigned = new boolean[m];
Arrays.fill(rowInd, -1);
Arrays.fill(colInd, -1);
for (int k = 0; k < n; k++) {
int minDist = Integer.MAX_VALUE;
int minIndex = -1;
for (int i = 0; i < n; i++) {
if (rowInd[i] != -1)
continue;
for (int j = 0; j < m; j++) {
if (assigned[j])
continue;
if (costMatrix[i][j] < minDist) {
minDist = costMatrix[i][j];
minIndex = j;
}
}
}
rowInd[k] = minIndex;
colInd[minIndex] = k;
assigned[minIndex] = true;
}
// Calculate the total minimum distance by the
// summing the assigned costs
int minTotalDistance = 0;
for (int i = 0; i < n; i++) {
minTotalDistance += costMatrix[i][rowInd[i]];
}
return minTotalDistance;
}
// Example usage
public static void main(String[] args)
{
int[][] drivers = { { 0, 0 }, { 2, 1 } };
int[][] packages = { { 1, 2 }, { 3, 3 } };
System.out.println(
assignPackages(drivers, packages));
}
}
import numpy as np
from scipy.optimize import linear_sum_assignment
def manhattan_distance(point1, point2):
return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])
def assign_packages(drivers, packages):
n = len(drivers)
m = len(packages)
# Create the cost matrix for each driver-package pair
cost_matrix = np.zeros((n, m))
for i in range(n):
for j in range(m):
cost_matrix[i][j] = manhattan_distance(drivers[i], packages[j])
# Apply the Hungarian algorithm to find the minimum cost assignment
row_ind, col_ind = linear_sum_assignment(cost_matrix)
# Calculate the total minimum distance by summing the assigned costs
min_total_distance = np.sum(cost_matrix[row_ind, col_ind])
return min_total_distance
# Driver code
drivers = [[0, 0], [2, 1]]
packages = [[1, 2], [3, 3]]
print(assign_packages(drivers, packages))
# Note : install scipy before running the code( pip install scipy)
function manhattanDistance(point1, point2) {
return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
}
function assignPackages(drivers, packages) {
const n = drivers.length;
const m = packages.length;
// Create the cost matrix for each driver-package pair
const costMatrix = new Array(n).fill().map(() => new Array(m));
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
costMatrix[i][j] = manhattanDistance(drivers[i], packages[j]);
}
}
// Apply the Hungarian algorithm to find the minimum cost assignment
const rowInd = new Array(n).fill(-1);
const colInd = new Array(m).fill(-1);
const assigned = new Array(m).fill(false);
for (let k = 0; k < n; k++) {
let minDist = Number.MAX_SAFE_INTEGER;
let minIndex = -1;
for (let i = 0; i < n; i++) {
if (rowInd[i] !== -1) continue;
for (let j = 0; j < m; j++) {
if (assigned[j]) continue;
if (costMatrix[i][j] < minDist) {
minDist = costMatrix[i][j];
minIndex = j;
}
}
}
rowInd[k] = minIndex;
colInd[minIndex] = k;
assigned[minIndex] = true;
}
// Calculate the total minimum distance by summing the assigned costs
let minTotalDistance = 0;
for (let i = 0; i < n; i++) {
minTotalDistance += costMatrix[i][rowInd[i]];
}
return minTotalDistance;
}
// Example usage
const drivers = [[0, 0], [2, 1]];
const packages = [[1, 2], [3, 3]];
console.log(assignPackages(drivers, packages));
Output
6
Time Complexity: O(n^3), where n is the maximum number of drivers or packages.
Auxiliary space: O(n^2), due to the storage of the cost matrix which is of size n×m.
Contact Us