To‘liq qidiruv
To‘liq qidiruv (complete search) degani chekli qidiruv fazosidagi barcha nomzodlarni sanab chiqish va shartni qanoatlantiradigan / qiymatni optimalini tanlash yoki sanashdir.
ta element () berilgan bo‘lsa, to‘plam ostini bitmask orqali ifodalash mumkin, bunda -bit element tanlangan-tanlanmaganini bildiradi. To‘plam ostilari soni: .
Permutatsiya — ta elementning tartiblanishidir. Permutatsiyalar soni: .
Har bir maska uchun dan gacha:
indeksdagi rekursiv funksiya:
Permutatsiyani pozitsiya bo‘yicha qurish:
ta butun son va maqsad berilgan. Yig‘indisi ga teng bo‘lgan to‘plam osti mavjudligini aniqlang.
ta manfiy bo‘lmagan butun sonlar va berilgan. Yig‘indisi bo‘lgan nechta to‘plam osti borligini hisoblang.
ta shahar va to‘liq masofa matritsasi berilgan. -shahardan boshlanib, har bir shaharni aynan bir marta ziyorat qiladigan va istalgan joyda tugaydigan marshrutning minimal qiymatini toping.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long T;
cin >> n >> T;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
long long sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) sum += a[i];
}
if (sum == T) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
long long n, S;
vector<long long> a;
long long ans = 0;
void rec(int i, long long sum) {
if (sum > S) return;
if (i == (int)n) {
ans++;
return;
}
rec(i + 1, sum); // skip
rec(i + 1, sum + a[i]); // take
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> S;
a.resize(n);
for (int i = 0; i < (int)n; i++) cin >> a[i];
rec(0, 0);
cout << ans << "\n";
return 0;
}
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int n;
vector<vector<long long>> d;
vector<int> path;
vector<int> used;
long long best = (1LL << 62);
void rec(int depth, int last, long long cost) {
if (cost >= best) return;
if (depth == n) {
best = min(best, cost);
return;
}
for (int v = 1; v < n; v++) {
if (used[v] == 0) {
used[v] = 1;
rec(depth + 1, v, cost + d[last][v]);
used[v] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
d.assign(n, vector<long long>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> d[i][j];
used.assign(n, 0);
used[0] = 1;
rec(1, 0, 0);
cout << best << "\n";
return 0;
}