Bitmask Dynamic Programming (DP) Overview

# Common bitmask operations
mask = 0b1101  # 13 in decimal

# Check if bit i is set
def is_set(mask, i):
    return (mask & (1 << i)) != 0

# Set bit i
def set_bit(mask, i):
    return mask | (1 << i)

# Clear bit i
def clear_bit(mask, i):
    return mask & ~(1 << i)

# Toggle bit i
def toggle_bit(mask, i):
    return mask ^ (1 << i)

# Count set bits
def count_bits(mask):
    return bin(mask).count('1')

# Example:
print(is_set(13, 0))    # True (bit 0 is 1)
print(is_set(13, 1))    # False (bit 1 is 0)
print(set_bit(13, 1))   # 15 (1101 | 0010 = 1111)

# Basic bitmask operations for subset problems
def solve_with_bitmask(n):
    # Generate all possible subsets
    for mask in range(1 << n):  # 2^n subsets
        # Check which elements are included
        for i in range(n):
            if mask & (1 << i):  # Element i is included
                # Process element i
                pass
    
    # Example: Find all subsets of [1, 2, 3]
    elements = [1, 2, 3]
    for mask in range(1 << 3):
        subset = []
        for i in range(3):
            if mask & (1 << i):
                subset.append(elements[i])
        print(f"Mask {mask:03b} = {subset}")

# Output:
# Mask 000 = []
# Mask 001 = [1]
# Mask 010 = [2]
# Mask 011 = [1, 2]
# Mask 100 = [3]
# Mask 101 = [1, 3]
# Mask 110 = [2, 3]
# Mask 111 = [1, 2, 3]

import math

def tsp_bitmask(dist):
    """
    Solve TSP using bitmask DP
    dist: distance matrix (n x n)
    Returns: minimum cost of complete tour
    """
    n = len(dist)
    
    # dp[mask][i]: minimum cost to reach city i having visited cities in mask
    dp = [[math.inf] * n for _ in range(1 << n)]
    
    # Base case: start at city 0 with only city 0 visited
    dp[1][0] = 0  # mask=0001, city=0, cost=0
    
    # Iterate over all possible subsets (masks)
    for mask in range(1 << n):
        # For each possible ending city
        for u in range(n):
            # Check if city u is visited in current mask
            if not (mask & (1 << u)):
                continue
            
            # Try to go to each unvisited city
            for v in range(n):
                # Skip if city v is already visited or same as u
                if mask & (1 << v) or u == v:
                    continue
                
                # New mask after visiting city v
                next_mask = mask | (1 << v)
                
                # Update minimum cost
                dp[next_mask][v] = min(
                    dp[next_mask][v],
                    dp[mask][u] + dist[u][v]
                )
    
    # Return to starting city (0) from any city
    final_mask = (1 << n) - 1  # All cities visited (1111...)
    return min(
        dp[final_mask][i] + dist[i][0] 
        for i in range(1, n)  # Don't include city 0 (already there)
    )

# Example usage:
distances = [
    [0, 2, 9, 10],
    [2, 0, 6, 4],
    [9, 6, 0, 3],
    [10, 4, 3, 0]
]

print(tsp_bitmask(distances))  # Output: 21 (A→B→D→C→A)

def subset_sum_bitmask(nums, target):
    """
    Check if any subset sums to target using bitmask
    nums: array of positive integers
    target: target sum
    Returns: True if subset exists, False otherwise
    """
    n = len(nums)
    
    # Try all possible subsets
    for mask in range(1 << n):
        subset_sum = 0
        
        # Calculate sum of current subset
        for i in range(n):
            if mask & (1 << i):  # Element i is included
                subset_sum += nums[i]
        
        # Check if this subset sums to target
        if subset_sum == target:
            # Print the subset for verification
            subset = [nums[i] for i in range(n) if mask & (1 << i)]
            print(f"Found subset: {subset}")
            return True
    
    return False

# Example:
nums = [1, 2, 3, 4, 5]
target = 7
print(subset_sum_bitmask(nums, target))  # True (subset [2,5] or [3,4])

def assignment_bitmask(cost):
    """
    Solve assignment problem using bitmask DP
    cost: cost matrix (n x n) where cost[i][j] = cost of assigning task i to worker j
    Returns: minimum total cost
    """
    n = len(cost)
    
    # dp[mask]: minimum cost to assign tasks represented by mask
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # Base case: no tasks assigned
    
    # For each possible assignment state
    for mask in range(1 << n):
        # Count how many tasks are assigned
        task_count = bin(mask).count('1')
        
        # Try assigning task task_count to each worker
        for worker in range(n):
            # Check if worker is available (not assigned yet)
            if not (mask & (1 << worker)):
                # Assign task task_count to worker
                new_mask = mask | (1 << worker)
                dp[new_mask] = min(
                    dp[new_mask],
                    dp[mask] + cost[task_count][worker]
                )
    
    return dp[(1 << n) - 1]  # All tasks assigned

# Example:
cost_matrix = [
    [3, 2, 1],  # Task 0 costs
    [4, 1, 2],  # Task 1 costs
    [2, 3, 1]   # Task 2 costs
]

print(assignment_bitmask(cost_matrix))  # Output: 4 (optimal assignment)

from functools import lru_cache

@lru_cache(maxsize=None)
def solve_with_memo(mask, pos):
    """Memoized bitmask DP"""
    if mask == (1 << n) - 1:  # All elements processed
        return 0
    
    # Try all possible next moves
    for next_pos in range(n):
        if not (mask & (1 << next_pos)):
            new_mask = mask | (1 << next_pos)
            # Recursive call with memoization
            result = solve_with_memo(new_mask, next_pos)
            # Process result...
    
    return best_result

# Instead of storing full state, compress to bitmask
def compress_state(visited, current_pos):
    """Compress state to bitmask"""
    mask = 0
    for i, v in enumerate(visited):
        if v:
            mask |= (1 << i)
    return mask, current_pos

# Skip states that can't lead to optimal solution
def is_valid_state(mask, additional_constraints):
    """Check if state is valid"""
    # Add your validation logic here
    return True