определение
Жадный алгоритм (также известный как жадный алгоритм) означает, что при решении задачи он всегда делает лучший выбор на данный момент. То есть вместо того, чтобы рассматривать общую оптимальность, то, что он сделал, является в некотором смысле локальным оптимальным решением.
Обычно код жадного алгоритма очень короткий, а идея очень проста, но реальная трудность жадного алгоритма состоит в том, чтобы определить, действительно ли наша текущая задача может использовать жадный алгоритм.
leetcode 455. Распространение файлов cookie
Идеи решения проблем
Это простая задача жадного алгоритма. Мы пытаемся дать самое большое печенье самому жадному ребенку.Если самый жадный ребенок может быть удовлетворен, то печенье, которое мы оставляем следующему жадному ребенку, также является самым большим на данный момент. Если самое большое печенье не может удовлетворить самого жадного ребенка, значит, ребенок не может быть удовлетворен.
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end(), greater<int>());
sort(s.begin(), s.end(), greater<int>());
int gi = 0, si = 0;
int res = 0;
while( gi < g.size() && si < s.size() ){
if( s[si] >= g[gi] ){
res ++;
si ++;
gi ++;
} else {
gi ++;
}
}
return res;
}
};
Жадные алгоритмы, как правило, неотделимы от сортировки, и если задача выдает, что массив не отсортирован, нам нужно отсортировать его самостоятельно.
Связь между жадным алгоритмом и динамическим программированием
метод динамического программирования
Идеи решения проблем
Мы можем сначала подумать о решении методом грубой силы: найти комбинацию всех подынтервалов, а затем определить, перекрываются ли они. О ((2 ^ п) * п)
Сначала отсортируйте их, чтобы было легче судить о том, что они не перекрываются.
Эта задача очень похожа на самую длинную возрастающую подпоследовательность, которую сначала решим с помощью динамического программирования:
выполнить
// Definition for an interval.
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
bool compare(const Interval &a, const Interval &b){
if( a.start != b.start )
return a.start < b.start;
return a.end < b.end;
}
// 动态规划
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
if( intervals.size() == 0 ) {
return 0;
}
sort(intervals.begin(), intervals.end(), compare);
// memo[i]表示以intervals[i]为结尾的区间能构成的最长不重叠区间序列
vector<int> memo( intervals.size() , 1 );
for( int i = 1 ; i < intervals.size() ; i ++ ) {
// memo[i]
for( int j = 0 ; j < i ; j ++ ) {
if( intervals[i].start >= intervals[j].end ) {
memo[i] = max( memo[i] , 1 + memo[j] );
}
}
}
int res = 0;
for( int i = 0 ; i < memo.size() ; i ++ ) {
res = max( res , memo[i] );
}
return intervals.size() - res;
}
};
Решение жадного алгоритма
Идеи решения проблем
Примечание. В каждом выборе важен конец каждого интервала.
Чем меньше окончание, тем больше места остается позади и тем больше вероятность того, что оно вместит больше интервалов.
Жадный алгоритм: сортировка по концу интервала и выбор интервала с самым ранним концом каждый раз, когда он не пересекается с предыдущим интервалом.
выполнить
// Definition for an interval.
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
bool compare(const Interval &a, const Interval &b){
if( a.end != b.end )
return a.end < b.end;
return a.start < b.start;
}
// 贪心算法
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
if( intervals.size() == 0 ) {
return 0;
}
sort(intervals.begin(), intervals.end(), compare);
int res = 1;
int pre = 0;
for( int i = 1 ; i < intervals.size() ; i ++ ) {
if( intervals[i].start >= intervals[pre].end ){
res ++;
pre = i;
}
}
return intervals.size() - res;
}
};
Доказательство свойств жадного выбора
- Жадный алгоритм — это А, оптимальный алгоритм — О, установлено, что А может полностью заменить О, не затрагивая оптимальное решение.
- Если жадный алгоритм использовать нельзя, приведите контрпример.
------------------------- Великолепная разделительная линия --------------------
Друзья, которые прочитали это, могут лайкнуть / подписаться, ваша поддержка - самая большая поддержка для меня.
личный блогСтек томатной технологиииДомашняя страница Наггетс
Если вы хотите узнать больше, обратите внимание на мой публичный аккаунт в WeChat: Tomato Technology Stack.