BOJ. Determine task (1311)

On this page

Problem: BOJ 1311 — Assignment

There are N people and N tasks. Assign each person exactly one task, with each task used once, so that the sum of the assignment costs is minimized.

Bitmask dynamic programming

Let dp[mask] be the minimum cost after assigning the first Integer.bitCount(mask) people to exactly the tasks whose bits are set in mask. The next person is therefore Integer.bitCount(mask). For every task not yet assigned, set its bit and add that person’s cost:

dp[mask | (1 << task)] = min(dp[mask | (1 << task)], dp[mask] + cost[person][task]).

The empty mask starts with cost 0; all other states start at INF. The full mask contains all tasks, so its value is the answer. This bottom-up form naturally retains zero-cost states. With N <= 20 and costs at most 1,000,000, any complete assignment costs at most 20,000,000, safely below INF = 1,000,000,000.

There are 2^N masks and at most N transitions per mask, so the time complexity is O(N * 2^N) and the space complexity is O(2^N).

Java

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    private static final int INF = 1_000_000_000;

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int[][] cost = new int[n][n];
        for (int person = 0; person < n; person++) {
            for (int task = 0; task < n; task++) {
                cost[person][task] = input.nextInt();
            }
        }

        int stateCount = 1 << n;
        int[] dp = new int[stateCount];
        for (int mask = 1; mask < stateCount; mask++) {
            dp[mask] = INF;
        }

        for (int mask = 0; mask < stateCount; mask++) {
            int person = Integer.bitCount(mask);
            if (person == n) {
                continue;
            }

            for (int task = 0; task < n; task++) {
                int taskBit = 1 << task;
                if ((mask & taskBit) == 0) {
                    int nextMask = mask | taskBit;
                    dp[nextMask] = Math.min(
                        dp[nextMask],
                        dp[mask] + cost[person][task]
                    );
                }
            }
        }

        System.out.println(dp[stateCount - 1]);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}