基礎編2——欲張り法

欲張りアルゴリズムとは,問題を解く際に,常に現在から見れば最良の選択を行うことである.すなわち,全体の最適化を考慮せずに,ある意味での局所最適解にすぎない.貪欲アルゴリズムはすべての問題に対して全体の最適解を得ることができるわけではないが,範囲がかなり広い多くの問題に対して彼は全体の最適解あるいは全体の最適解の近似解を生み出すことができる.
古典的な例題:
1人の子供が1ドル未満の砂糖を買って、1ドルのお金を店員に渡した.店員は一番少ないコインで子供に探してほしいと思っています.2 5セント、1 0セント、5セント、および1セントの硬貨の数に制限されない値が提供されると仮定する.キャンディを売る値段を入力して、一番少ないおつりの個数を出力します.
分析:個数が少なければ少ないほど良い、すぐに取り戻す価値ができるだけ大きい

#include 
#include
using namespace std;

struct pa                        //     ，s，e       
{
    int s,e;
}a[1000];
int cmp(const pa&a,const pa&b)    //         pa  a，b  ，         
{
    return a.s>n)
    {
        for(i=0;i>a[i].s>>a[i].e;
        }
        sort(a,a+n,cmp);        //        
        max=0;
        for(i=0;i=a[j-1].e) sum++;   //             ，  ，sum++；
            }
            if(sum>max) max=sum;
        }
        cout<