Ҷустуҷӯи пурра
Ҷустуҷӯи пурра (brute force) маънои шумориши ҳамаи номзадҳо аз як фазои ҷустуҷӯи маҳдуд ва интихоби онҳое, ки як шартро қонеъ мекунанд / як қиматро оптимизатсия мекунанд, дорад.
Бо додани ашё (), як зермаҷмӯаро метавон бо битмаскаи ифода кард, ки дар он бит нишон медиҳад, ки оё ашёи интихоб шудааст. Шумораи зермаҷмӯаҳо: .
Ҷойивазкунӣ тартиб додани унсур аст. Шумораи ҷойивазкуниҳо: .
Барои ҳар як маскаи аз то :
Функсияи рекурсивӣ дар индекси :
Ҷойивазкуниро мавқеъ ба мавқеъ созед:
Бо додани адади бутун ва ҳадафи , муайян кунед, ки оё зермаҷмӯае вуҷуд дорад, ки ҷамъбасти он ба баробар бошад.
Бо додани ададҳои ғайриманфии ва , шуморед, ки чанд зермаҷмӯа ҷамъбасти доранд.
Бо додани шаҳр ва матритсаи пурраи масофаҳо , арзиши ҳадди ақали як масирро ёбед, ки аз шаҳри оғоз мешавад, ҳар як шаҳрро маҳз як бор боздид мекунад ва дар ҳар ҷо анҷом меёбад.
#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;
}