как дела

Жадный алгоритм означает, что при решении задачи он всегда делает лучший выбор на данный момент. То есть вместо того, чтобы рассматривать общую оптимальность, то, что он сделал, является в некотором смысле локальным оптимальным решением.

Основная идея жадного алгоритма состоит в том, чтобы действовать шаг за шагом, начиная с начального решения задачи.Согласно мере оптимизации, каждый шаг должен обеспечивать возможность получения локального оптимального решения. На каждом шаге рассматриваются только одни данные, и их выбор должен удовлетворять условиям локальной оптимизации. Если следующие данные и частичное оптимальное решение больше не являются допустимым решением, данные не будут добавляться к частичному решению до тех пор, пока не будут пронумерованы все данные или алгоритм больше не может быть добавлен.

Одним словом: не ищите оптимальности, ищите только возможные решения.

Выберите использование жадного алгоритма

Мы можем доказать это согласно двум важным свойствам закона жадности:Свойство жадного выбора и свойство оптимальной подструктуры.

1, жадный выбор

Что такое жадный выбор? Это также короткая строка от значения слова. Гавиш интересы глаз. В алгоритме он основан только на текущей существующей информации и не изменит этот выбор в будущем. (В этом основное отличие метода динамического планирования)

Итак, подробный вопрос. Чтобы определить, обладает ли она свойством жадного выбора, необходимо доказать, приводит ли каждый шаг жадного выбора в конечном итоге к общему оптимальному решению задачи.

2. Оптимальная подструктура

Когда оптимальное решение задачи включает в себя оптимальные решения ее подзадач, говорят, что задача имеет оптимальные свойства подструктуры.

Используйте жадную стратегию для получения оптимального решения в каждом преобразовании. Свойство оптимальной подструктуры проблемы является ключевой особенностью того, что проблема может быть решена с помощью жадного алгоритма или алгоритма динамического программирования. Каждая операция жадного алгоритма напрямую влияет на результат, в отличие от динамического программирования. Жадный алгоритм делает выбор для решения каждой подзадачи и не может вернуться назад, динамическое программирование выбирает текущую по предыдущему результату выбора и имеет функцию отката. Динамическое программирование в основном используется в двумерных или трехмерных задачах, тогда как жадное программирование обычно используется в одномерных задачах.

Основная мысль

Основная идея жадного алгоритма состоит в том, чтобы вызвать определенное начальное решение проблемы и продолжить шаг за шагом. В соответствии с мерой оптимизации каждый шаг должен обеспечить получение локального оптимального решения. Каждое значение STEP считает Данные и его выбор должны удовлетворять локальному оптимальному решению. Оптимизированные условия. Если следующие данные и частичная оптимальная сериализация решения больше не является возможным решением, модифицированные данные не будут добавлены в частичное решение, пока все данные не будут перечислены и воспроизведены, или алгоритм не может быть остановлен во время добавления.

1. Строить математические модели для описания проблемы;
2. Разделить решаемую проблему на несколько подзадач;
3. Решите каждую подзадачу, чтобы получить локальное оптимальное решение подзадачи;
4. Объедините локальные оптимальные решения решений подзадач в решение исходной задачи решения.

Характеристики алгоритма

1. По мере выполнения алгоритма накапливаются два других набора: один содержит рассмотренных и выбранных кандидатов, а другой содержит рассмотренных, но отброшенных кандидатов.
   
2. Существует функция проверки того, дает ли набор объектов-кандидатов ответ на вопрос. Эта функция не учитывает, является ли решение в данный момент оптимальным.
   
3. Существует также функция, проверяющая допустимость набора кандидатов, то есть можно ли добавить к набору еще кандидатов для получения решения. Как и в случае с предыдущей функцией, оптимальность решения в настоящее время не рассматривается.
   
4. Функция выбора может указать, какой из оставшихся кандидатов является наиболее многообещающим решением проблемы.
5. Наконец, целевая функция дает значение решения.
6. Чтобы решить задачу, необходимо найти набор объектов-кандидатов, составляющих решение, которое может оптимизировать целевую функцию, и жадный алгоритм действует шаг за шагом. Изначально набор кандидатов, выбранных алгоритмом, пуст. На каждом последующем шаге по функции выбора алгоритм выбирает наиболее перспективный объект для формирования решения из оставшихся объектов-кандидатов. Если добавить объект в набор невозможно, то объект отбрасывается и не рассматривается, в противном случае он добавляется в набор. Каждый раз набор расширяется и проверяется, является ли набор решением. Если жадный алгоритм работает правильно, первое найденное решение обычно является оптимальным.

Общий процесс решения

Использование жадного метода для решения может быть основано на следующих аспектах (и, наконец, соответствует реализации каждого шага кода), взяв в качестве примера размен денег:

1, набор кандидатов (C)

Передайте набор кандидатов C как возможное решение проблемы. (Окончательное решение берется из множества кандидатов C)

Например. В задаче о размене валюты различных номиналов составляют набор кандидатов.

2. Набор растворов (S)

После каждого жадного выбора кладите решение в S. Наконец-то получил полное решение

3. Решение

Проверить, является ли набор решений S полным решением задачи.

Например, в поисках проблемы изменить. Функция была решена точно равной сумме уплаченных денежных счетов.

4. Выберите функцию (выбрать)

Piggy стратегия. Это ключ к жадным методам, выберите наиболее перспективное решение проблемы.

(Эта функция выбора обычно связана с целевой функцией)

Например, в проблеме сдачи жадная стратегия заключается в выборе валюты с наибольшей номинальной стоимостью в наборе кандидатов.

5. Возможные функции

Увеличение того, возможен ли объект кандидата в наборе сбора. (Это удовлетворяет условию ограничения после увеличения следующего объекта)

Например.在找零钱问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。

пример

1. Проблема выбора деятельности

Существует n занятий a1, a2, ..., an, которые должны использовать один и тот же класс в один и тот же день, и класс может использоваться только одним занятием за раз. Каждое действие ai имеет время начала si и время окончания fi. После выбора действие ai занимает полуоткрытый интервал времени [si, fi). Если [si,fi] и [sj,fj] не перекрываются друг с другом, в этот день можно запланировать две активности ai и aj. Проблема состоит в том, чтобы организовать эти мероприятия так, чтобы как можно больше мероприятий можно было провести без конфликтов.

#include<cstdio>  
#include<iostream>   
#include<algorithm>   
using namespace std;      
int N;  
struct Act  
{  
    int start;  
    int end;  
}act[100010];  
  
bool cmp(Act a,Act b)    
{    
    return a.end<b.end;    
}   
  
int greedy_activity_selector()    
{    
    int num=1,i=1;     
    for(int j=2;j<=N;j++)    
    {    
        if(act[j].start>=act[i].end)    
        {    
            i=j;    
            num++;    
        }    
    }    
    return num;  
}  
  
int main()    
{    
    int t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d",&N);  
        for(int i=1;i<=N;i++)  
        {  
            scanf("%lld %lld",&act[i].start,&act[i].end);  
        }  
        act[0].start=-1;  
        act[0].end=-1;  
        sort(act+1,act+N+1,cmp);   
        int res=greedy_activity_selector();  
        cout<<res<<endl;    
    }  
}    

2. Проблема с раздачей монет

#include<iostream>
#include<algorithm>
using namespace std;
const int N=7; 
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};
  
int solve(int money) 
{
	int num=0;
	for(int i=N-1;i>=0;i--) 
	{
		int c=min(money/Value[i],Count[i]);
		money=money-c*Value[i];
		num+=c;
	}
	if(money>0) num=-1;
	return num;
}
 
int main() 
{
	int money;
	cin>>money;
	int res=solve(money);
	if(res!=-1) cout<<res<<endl;
	else cout<<"NO"<<endl;
}

3. Проблема рюкзака

Есть рюкзак вместимостью m = 150 кг. Есть 7 предметов, а предметы не могут быть разделены на любой размер. Требование состоит в том, чтобы максимизировать общее значение элементов, загруженных в рюкзак как можно больше, но не превышать общую мощность.

анализ проблемы
Целевая функция: максимизировать ∑pi так, чтобы сумма значений всех предметов pi в рюкзаке была наибольшей.

Ограничения: Общий вес загружаемых предметов не превышает вместимость рюкзака: ∑wi

Жадная стратегия:

(1) Согласно жадной стратегии каждый раз, когда выбирается и загружается в рюкзак предмет с наибольшей ценностью, является ли результат оптимальным?

(2) Можно ли получить оптимальное решение, если каждый раз выбирать предметы с наименьшим весом?

(2) Жадная стратегия: выбирайте наименьший вес.Ее контрпример аналогичен первой стратегии.

⑶ жадная стратегия: максимальное значение веса элементов выбранных единиц.

• разработка алгоритма:

1. Рассчитать стоимость единицы веса каждого предмета
2. Значение товаров на единицу по убыванию
3. Выбирайте предметы в зависимости от текущей оставшейся вместимости рюкзака.
4. Если вместимость рюкзака больше веса текущего предмета, то загружается текущий предмет. В противном случае отбросить текущий элемент, а затем выйти из цикла до конца.

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
    int w;
    int v;
    double avg;
}P;
bool cmp(P a,P b){
    return a.avg>b.avg;
}
int main(){
    P *p;
    int n,i,m;//n 物品个数 m背包容量
    while(cin>>n>>m){
        p=new P[n];
        for(i=0;i<n;i++){
            cin>>p[i].w>>p[i].v;
            p[i].avg=p[i].v/p[i].w*1.0;
        }
        sort(p,p+n,cmp);
        int maxvalue=0;
        for(i=0;i<n;i++){
            if(p[i].w<=m){
                m-=p[i].w;
                maxvalue+=p[i].v;
            }else{
                break;
            }
        }
        cout<<maxvalue<<endl;
    }
    return 0;
}