Битовая маска и динамическое программирование | Набор 1 (подсчитайте способы назначить уникальное ограничение для каждого человека)

Опубликовано: 21 Января, 2022

Рассмотрим приведенную ниже постановку задач.

Существует 100 различных типов крышек, каждый из которых имеет уникальный идентификатор от 1 до 100. Кроме того, есть «n» человек, у каждого из которых есть набор переменного количества крышек. Однажды все эти люди решают пойти на вечеринку в кепке, но, чтобы выглядеть уникально, они решили, что никто из них не будет носить кепку того же типа. Итак, посчитайте общее количество аранжировок или способов, чтобы ни на одном из них не было кепки одного типа.

Ограничения: 1 <= n <= 10 Пример:

Первая строка содержит значение n, следующие n строк содержат коллекции. 
всех n человек.
Вход: 
3
5 100 1 // Сборник от первого лица.
2 // Сборник от второго лица.
5 100 // Сборник от третьего лица.

Выход:
4
Объяснение: Все допустимые способы: (5, 2, 100), (100, 2, 5),
            (1, 2, 5) и (1, 2, 100)

Поскольку количество способов может быть большим, выведите по модулю 1000000007

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.
Простое решение - попробовать все возможные комбинации. Начните с выбора первого элемента из первого набора, пометки его как посещенного и повторения для остальных наборов. По сути, это решение на основе обратного отслеживания.

Лучшее решение - использовать битовую маску и DP . Давайте сначала познакомимся с битовой маской.

Что такое битовая маска?
Предположим, у нас есть набор элементов, пронумерованных от 1 до N. Если мы хотим представить подмножество этого набора, оно может быть закодировано последовательностью из N бит (мы обычно называем эту последовательность «маской»). В выбранном нами подмножестве i-й элемент принадлежит ему тогда и только тогда, когда установлен i-й бит маски, т.е. он равен 1. Например, маска 10000101 означает, что подмножество набора [1… 8 ] состоит из элементов 1, 3 и 8. Мы знаем, что для набора из N элементов всего 2 N подмножеств, поэтому возможно 2 N масок, по одной, представляющей каждое подмножество. Фактически каждая маска представляет собой целое число, записанное в двоичной системе счисления.

Наша основная методология состоит в том, чтобы присвоить значение каждой маске (и, следовательно, каждому подмножеству) и, таким образом, вычислить значения для новых масок, используя значения уже вычисленных масок. Обычно наша основная цель - вычислить значение / решение для полного набора, то есть для маски 11111111. Обычно, чтобы найти значение для подмножества X, мы удаляем элемент всеми возможными способами и используем значения для полученных подмножеств X ' 1 , X' 2 …, X ' k, чтобы вычислить значение / решение для X. Это означает, что значения для X' i уже должны быть вычислены, поэтому нам нужно установить порядок, в котором маски будут рассматриваться. Легко увидеть, что подойдет естественный порядок: переходите по маскам в порядке возрастания соответствующих чисел. Кроме того, иногда мы начинаем с пустого подмножества X, добавляем элементы всеми возможными способами и используем значения полученных подмножеств X ' 1 , X' 2 …, X ' k для вычисления значения / решения для X.

В основном мы используем следующие обозначения / операции над масками:
bit (i, mask) - i-й бит маски
count (mask) - количество ненулевых битов в маске
first (mask) - номер младшего ненулевого бита в маске
set (i, mask) - установить i-й бит в маске
check (i, mask) - проверить i-й бит в маске

Как эта проблема решается с помощью Bitmasking + DP?
Идея состоит в том, чтобы использовать тот факт, что здесь до 10 человек. Таким образом, мы можем использовать целочисленную переменную в качестве битовой маски, чтобы запомнить, какой человек носит кепку, а какой нет.

Пусть i будет текущим номером крышки (крышки от 1 до i-1 уже 
обработанный). Пусть маска целочисленной переменной указывает, что лица w
ухо и не носить шапки. Если в маске установлен i-й бит, то 
На i'th человек кепка, иначе нет.

             // рассмотрим случай, когда i-й колпачок не включен 
                     // в аранжировке
countWays (маска, i) = countWays (маска, i + 1) +             
                    
                    // если в аранжировке есть i-й колпачок
                    // итак, присваиваем этот колпачок всем возможным лицам 
                    // один за другим и повторяем для остальных.
                    ∑ countWays (маска | (1 << j), i + 1)
                       для каждого человека j, который может носить кепку i 
 
Обратите внимание, что выражение «маска | (1 << j)» устанавливает j-й бит маски.
И человек может носить кепку i, если она есть в списке кепки человека
предоставлен в качестве входных данных.

Если мы нарисуем полное дерево рекурсии, мы увидим, что многие подзадачи решаются снова и снова. Итак, мы используем динамическое программирование. Таблица dp [] [] используется так, что в каждой записи dp [i] [j], i - маска, а j - номер крышки.

Поскольку мы хотим получить доступ ко всем людям, которые могут носить данную кепку, мы используем массив векторов capList [101]. Значение capList [i] указывает список лиц, которые могут носить кепку i.

Below is the implementation of above idea.

C/C++

// C++ program to find number of ways to wear hats
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
  
// capList[i]"th vector contains the list of persons having a cap with id i
// id is between 1 to 100 so we declared an array of 101 vectors as indexing
// starts from 0.
vector<int> capList[101];
  
// dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that
// how many and which persons are wearing cap. j denotes the first j caps
// used. So, dp[i][j] tells the number ways we assign j caps to mask i
// such that none of them wears the same cap
int dp[1025][101];
  
// This is used for base case, it has all the N bits set
// so, it tells whether all N persons are wearing a cap.
int allmask;
  
// Mask is the set of persons, i is cap-id (OR the 
// number of caps processed starting from first cap).
long long int countWaysUtil(int mask, int i)
{
    // If all persons are wearing a cap so we
    // are done and this is one way so return 1
    if (mask == allmask) return 1;
  
    // If not everyone is wearing a cap and also there are no more
    // caps left to process, so there is no way, thus return 0;
    if (i > 100) return 0;
  
    // If we already have solved this subproblem, return the answer.
    if (dp[mask][i] != -1) return dp[mask][i];
  
    // Ways, when we don"t include this cap in our arrangement
    // or solution set.
    long long int ways = countWaysUtil(mask, i+1);
  
    // size is the total number of persons having cap with id i.
    int size = capList[i].size();
  
    // So, assign one by one ith cap to all the possible persons
    // and recur for remaining caps.
    for (int j = 0; j < size; j++)
    {
        // if person capList[i][j] is already wearing a cap so continue as
        // we cannot assign him this cap
        if (mask & (1 << capList[i][j])) continue;
  
        // Else assign him this cap and recur for remaining caps with
        // new updated mask vector
        else ways += countWaysUtil(mask | (1 << capList[i][j]), i+1);
        ways %= MOD;
    }
  
    // Save the result and return it.
    return dp[mask][i] = ways;
}
  
// Reads n lines from standard input for current test case
void countWays(int n)
{
    //----------- READ INPUT --------------------------
    string temp, str;
    int x;
    getline(cin, str);  // to get rid of newline character
    for (int i=0; i<n; i++)
    {
        getline(cin, str);
        stringstream ss(str);
  
        // while there are words in the streamobject ss
        while (ss >> temp)
        {
            stringstream s;
            s << temp;
            s >> x;
  
            // add the ith person in the list of cap if with id x
            capList[x].push_back(i);
        }
    }
    //----------------------------------------------------
  
    // All mask is used to check whether all persons
    // are included or not, set all n bits as 1
    allmask = (1 << n) - 1;
  
    // Initialize all entries in dp as -1
    memset(dp, -1, sizeof dp);
  
    // Call recursive function count ways
    cout << countWaysUtil(0, 1) << endl;
}
  
// Driver Program
int main()
{ 
     int n;   // number of persons in every test case
     cin >> n;
     countWays(n);
     return 0;
}

Java

// Java program to find number of ways to wear hats
  
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Vector;
  
class Test
{
    static final int MOD = 1000000007;
      
    // for input
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
    // capList[i]"th vector contains the list of persons having a cap with id i
    // id is between 1 to 100 so we declared an array of 101 vectors as indexing
    // starts from 0.
    static Vector<Integer> capList[] = new Vector[101];
      
       
    // dp[2^10][101] .. in dp[i][j], i denotes the mask i.e., it tells that
    // how many and which persons are wearing cap. j denotes the first j caps
    // used. So, dp[i][j] tells the number ways we assign j caps to mask i
    // such that none of them wears the same cap
    static int dp[][] = new int[1025][101];
       
    // This is used for base case, it has all the N bits set
    // so, it tells whether all N persons are wearing a cap.
    static int allmask;
       
    // Mask is the set of persons, i is cap-id (OR the 
    // number of caps processed starting from first cap).
    static long countWaysUtil(int mask, int i)
    {
        // If all persons are wearing a cap so we
        // are done and this is one way so return 1
        if (mask == allmask) return 1;
       
        // If not everyone is wearing a cap and also there are no more
        // caps left to process, so there is no way, thus return 0;
        if (i > 100) return 0;
       
        // If we already have solved this subproblem, return the answer.
        if (dp[mask][i] != -1) return dp[mask][i];
       
        // Ways, when we don"t include this cap in our arrangement
        // or solution set.
        long ways = countWaysUtil(mask, i+1);
       
        // size is the total number of persons having cap with id i.
        int size = capList[i].size();
       
        // So, assign one by one ith cap to all the possible persons
        // and recur for remaining caps.
        for (int j = 0; j < size; j++)
        {
            // if person capList[i][j] is already wearing a cap so continue as
            // we cannot assign him this cap
            if ((mask & (1 << capList[i].get(j))) != 0) continue;
       
            // Else assign him this cap and recur for remaining caps with
            // new updated mask vector
            else ways += countWaysUtil(mask | (1 << capList[i].get(j)), i+1);
            ways %= MOD;
        }
       
        // Save the result and return it.
        return dp[mask][i] = (int) ways;
    }
       
    // Reads n lines from standard input for current test case
    static void countWays(int n) throws Exception
    {
        //----------- READ INPUT --------------------------
        String str;
        String split[];
        int x;
                
        for (int i=0; i<n; i++)
        {
            str = br.readLine();
            split = str.split(" ");
            
            // while there are words in the split[]
            for (int j = 0; j < split.length; j++) {
                 // add the ith person in the list of cap if with id x
                x = Integer.parseInt(split[j]);
                capList[x].add(i);
            }
            
        }
        //----------------------------------------------------
       
        // All mask is used to check of all persons
        // are included or not, set all n bits as 1
        allmask = (1 << n) - 1;
       
        // Initialize all entries in dp as -1
        for (int[] is : dp) {
            for (int i = 0; i < is.length; i++) {
                is[i] = -1;
            }
        }
       
        // Call recursive function count ways
        System.out.println(countWaysUtil(0, 1));
    }
  
    // Driver method
    public static void main(String args[]) throws Exception
    {
        int n;   // number of persons in every test case
          
        // initializing vector array
        for (int i = 0; i < capList.length; i++)
            capList[i] = new Vector<>();
          
          
        n = Integer.parseInt(br.readLine());
        countWays(n);
    }
}
// This code is contributed by Gaurav Miglani

Python

#Python program to find number of ways to wear hats
from collections import defaultdict
  
class AssignCap:
  
    # Initialize variables
    def __init__(self):
  
            self.allmask = 0
  
            self.total_caps = 100
  
            self.caps = defaultdict(list)
  
  
    #  Mask is the set of persons, i is the current cap number.
    def countWaysUtil(self,dp, mask, cap_no):
          
        # If all persons are wearing a cap so we
        # are done and this is one way so return 1
        if mask == self.allmask:
            return 1
  
        # If not everyone is wearing a cap and also there are no more
        # caps left to process, so there is no way, thus return 0;
        if cap_no > self.total_caps:
            return 0
  
        # If we have already solved this subproblem, return the answer.
        if dp[mask][cap_no]!= -1 :
            return dp[mask][cap_no]
  
        # Ways, when we don"t include this cap in our arrangement
        # or solution set
        ways = self.countWaysUtil(dp, mask, cap_no + 1)
          
        # assign ith cap one by one  to all the possible persons
        # and recur for remaining caps.
        if cap_no in self.caps:
  
            for ppl in self.caps[cap_no]:
                  
                # if person "ppl" is already wearing a cap then continue
                if mask & (1 << ppl) : continue
                  
                # Else assign him this cap and recur for remaining caps with
                # new updated mask vector
                ways += self.countWaysUtil(dp, mask | (1 << ppl), cap_no + 1) 
  
                ways = ways % (10**9 + 7)
  
        # Save the result and return it
        dp[mask][cap_no] = ways
  
        return dp[mask][cap_no]
  
  
  
    def countWays(self,N):
  
        # Reads n lines from standard input for current test case
        # create dictionary for cap. cap[i] = list of person having
        # cap no i
        for ppl in range(N):
  
            cap_possessed_by_person = map(int, raw_input().strip().split())
  

РЕКОМЕНДУЕМЫЕ СТАТЬИ