資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中的位掩碼和動態規劃
首先，我們將學習位掩碼和動態規劃，然後我們將解決一個相關的問題，這將解決您與實現相關的疑問。
位掩碼，也稱為掩碼，是 N 位的序列，用於編碼集合的子集。掩碼的元素可以是設定的或未設定的（即 0 或 1）。這表示位掩碼中所選元素的可用性。例如，如果掩碼的第 i 位被設定，則元素 i 在子集中可用。對於 N 個元素的集合，可以有 2N 個掩碼，每個掩碼對應一個子集。
因此，為了解決問題，我們將從一個掩碼（即子集）開始，為其分配一個值，然後使用先前掩碼的值查詢後續掩碼的值。使用此方法，我們將最終能夠計算主集合的值。
為了計算掩碼的最優解，我們將以所有可能的方式移除一個元素，並計算所有這些值，這些值將最終有助於最終解。
動態規劃
動態規劃是一種最佳化方法，其中我們解決子問題並將它們的解儲存起來，以便在其他重疊的子問題中使用。
現在，讓我們來看一個我們將使用位掩碼和動態規劃來解決的問題
問題
有 50 個帽子，編號從 1 到 50。N 個人在其收藏中有一些帽子。有一天，他們都戴著帽子去參加派對。但所有人都需要看起來獨一無二，所以他們決定每個人都戴不同號碼的帽子。我們得到 n 個人的數量以及他們收藏中的帽子號碼。我們的任務是找到他們可以戴帽子的總方法數，以便每個人看起來都獨一無二。
在這個問題中，第一行包含值 n，即人數。接下來的 n 行包含他們的收藏。
輸入 −
3 4 45 10 25 45 10
輸出 −
4
說明 −
所有可能的方法是(4, 25, 45) , (4, 25, 10), (45, 25, 10), (10, 25, 45)。
輸出應為 1000000007 的形式，因為方法的數量可能很大。
要解決此問題，一個簡單的解決方案是使用帽子查詢所有可能的人員組合。從第一個集合開始，遞迴其餘集合。但此解決方案未經最佳化。
更好的解決方案是使用位掩碼和動態規劃，為 10 個人建立一個大小為 210 的掩碼。以及大小為 51 的帽子向量。然後，我們將以多種方式遞迴。
示例
展示解決方案實現的程式 −
#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
if (mask == allmask) return 1;
if (i > 100) return 0;
if (dp[mask][i] != -1) return dp[mask][i];
long long int ways = uniqueCaps(mask, i+1);
int size = caps[i].size();
for (int j = 0; j < size; j++) {
if (mask & (1 << caps[i][j])) continue;
else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
ways %= (1000000007);
}
return dp[mask][i] = ways;
}
int main() {
int n = 3;
// Collection of person 1
caps[4].push_back(0);
caps[45].push_back(0);
caps[10].push_back(0);
// Collection of person 2
caps[25].push_back(1);
// Collection of person 3
caps[45].push_back(2);
caps[10].push_back(2);
allmask = (1 << n) - 1;
memset(dp, -1, sizeof dp);
cout<<"The number of ways the person can wear unique cap in party is:\t"<<uniqueCaps(0, 1);
return 0;
}輸出
The number of ways the person can wear unique cap in party is: 4
3K+ 次瀏覽
