贪心算法是一种在每一步选择中都采取当前状态最优解的策略。本文涵盖五个典型例题:货仓选址利用中位数最小化距离;最大子段和通过维护前缀和最大值求解;纪念品分组采用排序后首尾配对策略;排座椅分别统计行列干扰次数并选取最大项;矩阵消除游戏则通过枚举列组合配合贪心选行。文章提供 C++ 代码实现及逻辑证明,适合算法初学者掌握贪心思想。
#include<iostream>#include<vector>#include<algorithm>usingnamespace std;
intmain(){
int n, m;
cin >> n >> m;
vector<int> v;
while (m--) {
int num;
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end());
int ret = 0;
int left = 0;
int right = v.size() - 1;
while (left <= right) {
int sum = v[left];
if (sum + v[right] <= n) left++;
ret++;
right--;
}
cout << ret;
return0;
}
#include<iostream>#include<vector>#include<algorithm>usingnamespace std;
intmain(){
int n, m, k;
cin >> n >> m >> k;
k = min(k, n + m);
vector<vector<int>> v(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int num;
cin >> num;
v[i][j] = num;
}
}
int ret = 0;
for (int i = 0; i < (1 << n); i++) {
int tmp1 = i;
int count = 0;
vector<int> bit;
for (int j = 0; j < n; j++) {
if ((tmp1 & (1 << j)) != 0) bit.push_back(j);
}
if (bit.size() > k) continue;
auto tmp = v;
int sum = 0;
for (int sz = 0; sz < bit.size(); sz++) {
for (int j = 0; j < m; j++) {
sum += tmp[bit[sz]][j];
tmp[bit[sz]][j] = 0;
}
}
if (bit.size() < k) {
vector<int> y(16, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) y[i] += tmp[j][i];
}
sort(y.begin(), y.end());
auto it = y.rbegin();
for (int i = 0; i < k - bit.size(); i++) {
sum += *it;
it++;
}
}
if (sum > ret) ret = sum;
}
cout << ret;
return0;
}