oi筆記——抽象的深度優先搜索
例題：
\(N個數中選K個數，選出的和要為sum\)
例題分析：
對于每個點，我們可以按“選”和“不選”進行搜索，如圖：
或者01背包求解
求解示例（抽象深搜版代碼）
#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i,int cnt,int s) {
if(i==n) {
if(cnt==k&&s==sum) {
ans++;
}
return;
}
dfs(i+1,cnt,s);
dfs(i+1,cnt+1,s+a[i]);
}
int main() {
cin >> n >> k >> sum;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ans = 0;
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
定義：
前面說過，dfs 看起來是運行在圖上的搜索演算法，而前一節給大家展示的 dfs 程序，我們沒有看到圖的存在，這就是抽象形式的 dfs 的特點，我們可以根據搜索狀態構建一張抽象的圖，圖上的一個頂點就是一個狀態，而圖上的邊就是狀態之間的轉移關系（進一步搜索或回溯），雖然 dfs 是在這張抽象的圖上進行的，但我們不必把這張圖真正地建立出來，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/73335.html
標籤：C++
上一篇：面向程序和面向物件