13518219792
貪心算法
創(chuàng)新互聯(lián)專注于祥符網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供祥符營(yíng)銷型網(wǎng)站建設(shè)，祥符網(wǎng)站制作、祥符網(wǎng)頁設(shè)計(jì)、祥符網(wǎng)站官網(wǎng)定制、微信平臺(tái)小程序開發(fā)服務(wù)，打造祥符網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供祥符網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。
1．概念
貪心算法是從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以
盡可能快地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)
前進(jìn)時(shí)，算法停止。這時(shí)就得到了問題的一個(gè)解，但不能保證求
得的最后解是最優(yōu)的。在改進(jìn)算法中，貪心算法演化為爬山法。
2．特點(diǎn)及使用范圍
貪心算法的優(yōu)點(diǎn)在于時(shí)間復(fù)雜度極底。貪心算法與其他最優(yōu)化算
法的區(qū)別在于：它具有不可后撤性，可以有后效性，一般情況下
不滿足最優(yōu)化原理。貪心算法的特點(diǎn)就決定了它的適用范圍，他
一般不適用于解決可行性問題，僅適用于較容易得到可行解的最
優(yōu)性問題。這里較容易得到可行解的概念是：當(dāng)前的策略選擇后，
不會(huì)或極少使后面出現(xiàn)無解的情況。另外，對(duì)于近年來出現(xiàn)的交
互性題目，貪心算法是一個(gè)較好的選擇。這是因?yàn)椋陬}目中，
一個(gè)策略的結(jié)果是隨題目的進(jìn)行而逐漸給出的，我們無法預(yù)先知
道所選策略的結(jié)果，這與貪心算法不考慮策略的結(jié)果和其具有后
效性的特點(diǎn)是不謀而合的。當(dāng)然，貪心算法還可以為搜索算法提
供較優(yōu)的初始界值。
LZ在開始研究ACM嘛？
#include
int
least_num_cash(int
_money)
{
/*直接貪心，能用大張的鈔票盡量用大張的*/
int
ret=0;
while(_money!=0)
{
if(_money=100)
{
_money-=100;
}
else
if(_money=50)
{
_money-=50;
}
else
if(_money=20)
{
_money-=20;
}
else
if(_money=10)
{
_money-=10;
}
else
if(_money=5)
{
_money-=5;
}
else
if(_money=2)
{
_money-=2;
}
else
if(_money=1)
{
_money-=1;
}
ret++;
}
return
ret;
}
int
main()
{
int
n,m;
while(scanf("%d%d",n,m)!=EOF)
{
printf("%d\n",least_num_cash(m-n));
}
return
0;
}
多塔問題？？
可用動(dòng)態(tài)規(guī)劃試一下。。
記錄m臺(tái)機(jī)器中使用時(shí)間最長(zhǎng)的，時(shí)間為Tmax，以及其它m-1臺(tái)機(jī)器所用時(shí)間為Ti。
將Ti與Tmax時(shí)間差的和記錄為St。則St越小時(shí)間Tmax越短。
