✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-221

Bitmask Dynamic Programming

Bitmask Dynamic Programming combines dynamic programming with bitmasks to represent subsets compactly and solve problems involving selections, assignments, and combinations.

Explanation

Overview

Bitmask Dynamic Programming, often called bitmask DP, is a technique in which an integer bitmask represents the current subset of selected elements. Dynamic programming states use this mask to remember which elements have already been processed, selected, or assigned.

Core idea

For n elements, a bitmask can represent any subset using n bits. A bit value of 1 means the corresponding element is included, while 0 means it is not included. There are 2^n possible subsets, making bitmask DP especially suitable for problems with relatively small n.

How it works

Assign each element a unique bit position.; Represent the current selected subset using an integer mask.; Define a DP state using the mask and any additional information required by the problem.; Initialize the state representing the empty subset.; Generate transitions by selecting an element whose bit is currently 0.; Update the DP value for the newly formed subset.

Key concepts

Subset representation; Bitmasks; Dynamic programming states; State transitions; Set-bit counting; Subset enumeration

Time complexity

operation: Number of subset states; complexity: O(2^n); operation: Transitions per state; complexity: O(n); operation: Typical total time; complexity: O(n × 2^n)

Space complexity

O(2^n) for a one-dimensional DP array. Additional state dimensions may increase memory requirements.

Example

scenario: Assigning three tasks to three workers, where each worker must receive exactly one task.; tasks: Task A; Task B; maskInterpretation: binary: 101; meaning: Task A and Task C have been assigned, while Task B remains unassigned.; stateExample: dp[mask] can represent the minimum cost of reaching the assignment state described by mask, with the next worker determined by the number of set bits.; explanation: The algorithm builds solutions by adding one unassigned task at a time. Each mask represents a unique collection of completed assignments.

Example or application

Scenario

Assigning three tasks to three workers, where each worker must receive exactly one task.

Tasks

  • Task A

  • Task B

  • Task C

Mask Interpretation

Binary

101

Meaning

Task A and Task C have been assigned, while Task B remains unassigned.

State Example

dp[mask] can represent the minimum cost of reaching the assignment state described by mask, with the next worker determined by the number of set bits.

Explanation

The algorithm builds solutions by adding one unassigned task at a time. Each mask represents a unique collection of completed assignments.

Definition

Bitmask Dynamic Programming, often called bitmask DP, is a technique in which an integer bitmask represents the current subset of selected elements. Dynamic programming states use this mask to remember which elements have already been processed, selected, or assigned.

Core Idea

For n elements, a bitmask can represent any subset using n bits. A bit value of 1 means the corresponding element is included, while 0 means it is not included. There are 2^n possible subsets, making bitmask DP especially suitable for problems with relatively small n.

How It Works

  • Assign each element a unique bit position.

  • Represent the current selected subset using an integer mask.

  • Define a DP state using the mask and any additional information required by the problem.

  • Initialize the state representing the empty subset.

  • Generate transitions by selecting an element whose bit is currently 0.

  • Update the DP value for the newly formed subset.

  • Read the required answer from the final relevant state.

State Definition

Description

A common assignment-problem state is dp[mask], where mask represents the tasks already assigned. The number of set bits indicates how many tasks have been assigned.

Transition

dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[nextWorker][j])

Condition

The transition is allowed only when bit j is not already set and task j is available.

Implementation

Language

Pseudocode

Code

  • function solveAssignment(cost, n):

  • INF = veryLargeNumber

  • dp = array of size (1 << n), filled with INF

  • dp[0] = 0

  • for mask from 0 to (1 << n) - 1:

  • worker = countSetBits(mask)

  • if worker == n:

  • continue

  • for task from 0 to n - 1:

  • if (mask & (1 << task)) == 0:

  • nextMask = mask | (1 << task)

  • dp[nextMask] = min(

  • dp[nextMask],

  • dp[mask] + cost[worker][task]

  • )

  • return dp[(1 << n) - 1]

Time Complexity

OperationComplexity

Number of subset states

O(2^n)

Transitions per state

O(n)

Typical total time

O(n × 2^n)

Space Complexity

O(2^n) for a one-dimensional DP array. Additional state dimensions may increase memory requirements.

Key Concepts

  • Subset representation

  • Bitmasks

  • Dynamic programming states

  • State transitions

  • Set-bit counting

  • Subset enumeration

  • Assignment optimization

Advantages

  • Represents subsets using a compact integer.

  • Avoids repeatedly storing complete subsets as collections.

  • Provides a systematic way to solve small-n combinatorial problems.

  • Combines naturally with memoization and tabulation.

  • Can handle assignment and subset-selection problems that are difficult to solve greedily.

Limitations

  • The number of states grows exponentially with n.

  • Memory usage becomes large when n increases.

  • The integer type must be able to represent the required bitmask.

  • State definitions and transitions can become difficult in complex problems.

Applications

  • Traveling Salesperson Problem

  • Assignment optimization

  • Task scheduling

  • Subset selection

  • Hamiltonian path problems

  • Matching and pairing problems

  • Small-state combinatorial optimization

Related Topics

  • Dynamic Programming

  • Bitwise Operators and Bitmasking

  • Subset Enumeration

  • Combinatorial Optimization

  • Traveling Salesperson Problem

Practice Questions

QuestionAnswer

What does one bitmask represent in bitmask DP?

A particular subset of selected or processed elements.

How many subsets can be represented using n bits?

2^n subsets.

Why is bitmask DP mainly suitable for small values of n?

Because its state count grows exponentially as 2^n.

What is the typical complexity of an assignment-style bitmask DP?

O(n × 2^n) time and O(2^n) space.

Learning Objectives

  • Explain the central idea and purpose of bitmask dynamic programming.

  • Identify the assumptions, inputs, and conditions relevant to bitmask dynamic programming.

  • Evaluate an application of bitmask dynamic programming for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures