concept · INFO-CS-ADS-221Bitmask 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.
Mask Interpretation
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
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
| Operation | Complexity |
|---|
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.
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
| Question | Answer |
|---|
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