Полный поиск
Полный перебор (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;
}