閱讀了一些資料，當做自己的讀書筆記，
1.貪心演算法簡介
1.1 基本定義
在貪婪演算法(greedy method) 中，我們要逐步構造一個最優解，每一步，我們都在一定的標準下，做出一個最優決策，做出決策所依據的標準稱為貪心準則(greedy criterion)，
貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇，
也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的區域最優解，
貪心演算法每一步必須滿足以下條件：
1、可行的：即它必須滿足問題的約束，
2、區域最優：他是當前步驟中所有可行選擇中最佳的區域選擇，
3、不可更改：即選擇一旦做出，在演算法的后面步驟就不可改變了，
注意:!!!
貪心演算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性，即某個狀態以后的程序不會影響以前的狀態，只與當前狀態有關，
貪心準則：在不超過要發的工資的條件下，每一次都選擇面值盡可能大的人民幣，直到湊成的面值總數等于要發的工資，
#include<iostream>
using namespace std;
//貪心演算法，
int count (int n)//定義一個函式，
{
int sum=0;
int a[6]={100,50,10,5,2,1};//人民幣的面值
for(int i=0;i<6;i++)
{
sum=sum+n/a[i];//一個老師的工資的張數
n=n%a[i];//一個數除以一個比自身大的數商為0，余數為本身，
}
return sum;
}
int main()
{
int n,a[100];
while(cin>>n)
{
int k=0;//注意要初始化
if(n==0)
{
break;
}
for(int i=0;i<n;i++)
{
cin>>a[i];//回圈得到老師的工資，
}
for(int j=0;j<n;j++)
{
k=count(a[j])+k;//呼叫函式，得到所有老師發的張數，
}
cout<<k<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252035.html
標籤：其他
下一篇：詳解青蛙跳臺階的遞回問題