狀態壓縮動態規劃算法
狀態壓縮動態規劃是動態規劃的一種,它通過使用位運算的方式壓縮程序占用的空間,對于可以用來解決一些只有兩個狀態(是與否)的問題。
多少無益,我們通過下面的一道編程題目來學習這種算法。
題目描述:
小明使用霰彈槍打固定靶,假設有M個目標,小明開了N槍。每一槍都有若干目標被命中。現在小明想知道,自己剛剛理論上最少只需要幾槍就能打中全部的目標。
假設有3個目標:[0, 0, 0]
小明開了3槍:[1, 0, 0],[0, 1, 0],[0, 1, 1],其中為1表示命中了對應的目標。
結果輸出:小明第一槍加第三槍命中了所有的目標,理論上只要兩槍就可以全部命中。
假設有3個目標:[0, 0, 0]
小明開了3槍:[1, 0, 0],[0, 1, 0],[1, 1, 0],其中為1表示命中了對應的目標。
結果輸出:小明無法全部命中目標。
分析:
這道題有很多不同解法,可以使用貪心算法,但是為了講解狀壓動規,這里不使用貪心算法。
使用動態規劃解決問題的第一步就是要確定使用動態規劃能否解決問題。題干中有一個關鍵詞,最少幾槍。更關鍵的一點是它沒有要求我輸出到底是哪幾槍(如果要求輸出哪幾槍可能就要用回溯子集了)。因此大家應該條件反射的嘗試使用動態規劃。
動態規劃最重要的一個步驟就是確定動態數組dp與狀態轉移矩陣。
確定dp數組的含義
首先確認dp的大小,有的同學可能條件反射的認為dp的大小應該是M,對應M個目標。dp[i]表示命中i個目標需要的最小槍數。但是接下來會發現舉步維艱,因為都是命中i個目標,如果打中不一樣的靶子,反應的是不同的狀態。實際上這道題的dp矩陣的索引的含義并不是直接了當的呈現在我們的面前。
提問:當我有M個目標時,我有多少種命中狀態?
答:每個目標都有命中與未命中兩種狀態,M個目標組合起來應該是2的M次方。
聰明的讀者到這里應該恍然大悟一下:原來dp要有2^M個元素,索引反應了目標的命中情況。假設dp[3] = 2,indx = 3的二進制是011b,這里表示命中前兩個目標最少需要2槍。
dp數組初始化
明確了dp數組的含義,就需要對dp數組進行初始化了,結合dp數組的含義,我們應該首先明確:
dp[0] = 0:命中0個目標需要開0槍。
假設小明第2槍命中情況為:[1, 0, 1],那么:
dp[101b] = dp[5] = 1:命中第一個與第三個目標只需要一槍。
我們將命中目標用二進制掩碼表示,將所有子彈命中的情況對應的dp[indx]置為1即可完成初始化。
這就是這個問題的解決思路,現在我們直接上代碼,一些細節用代碼來講述。
完整代碼
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;int main() {int M, N; // M個目標 開N槍cin >> M >> N; // 輸入 M 與 Nvector<int> state; // 裝填掩碼for (int i = 0; i < N; i++) {int s = 0;for (int j = 0; j < M; j++) {int tmp = 0;cin >> tmp; // 輸入第i槍命中情況,1:命中,0:未命中s = (s << 1) + tmp;}state.push_back(s);}// 對state內的所有數據按位取與,如果tmp = 2^M -1,證明N槍后所有目標都命中int tmp = 0;for (int i : state) {tmp |= i;}if (tmp != (1 << M) - 1) { cout << "未命中所有目標" << endl;return 0;}// 初始化dp數組int num = (1 << M) - 1;vector<int> dp(num + 1, INT_MAX);dp[0] = 0;for (int i : state) {dp[i] = 1;}// 狀態轉移,講解見后文for (int mask : state) {for (int indx = num; indx >= 0; indx--) {if (dp[indx] != INT_MAX) {int new_indx = indx | mask;if (dp[indx] + 1 < dp[new_indx]) {dp[new_indx] = dp[indx] + 1;}}}}cout << "最少需要" << dp[num] << "槍" << endl;return 0;
}
狀態轉移分析
假設當前命中狀態為x0
,在第k發子彈的射擊下,命中狀態x1
變為x1 = x0 | state[k];
。
從狀態x0到狀態x1,射擊次數變為:tmp_num = dp[x0] + 1
。
結合dp[x1]
的定義:命中狀態為x1
時,需要最少的的射擊次數。因此我們需要比較通過x0
轉移到x1
的射擊次數tmp_num
與dp[x1]
目前的值:
偽代碼:
int x1 = x0 | state[k]; // 這里表示一次射擊動作
int tmp_num = dp[x0] + 1;
if(tmp_num < dp[x1]) { dp[x1] = tmp_num; // 證明由x0到達x1比原本的方案更快 }
else { ; // 空操作,證明當前到達x1有更快的射擊方案 }
小結
上面的講解就是狀態壓縮動態規劃的一個使用案例與核心邏輯。
之所以選擇這種方法有三個關鍵要素:
1、求最優方案。
2、不要求輸出最優方案的具體路徑信息。
3、對于最小元素(一個目標),只有是和否(命中/未命中)兩種區別。