貪心算法的分析與實(shí)際應(yīng)用用時(shí)可以刪除天津師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院算法設(shè)計(jì)與分析結(jié)課論文專(zhuān)業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)1402班 學(xué)號(hào)56姓名王悅寧 而且說(shuō)給而且說(shuō)給出的算法一般比動(dòng)態(tài)規(guī)劃算法更加簡(jiǎn)法概述ithm優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。本文主要介紹了貪心ThegreedyalgorithmanalysisandpracticalapplicationAbstract：Greedyalgorithmrefersto,inthesolutionoftheproblem,alwaysmakeinthecurrentviewisthebestchoice.Thatistosay,nottobeconsideredasawhole,hemadeonlyinasenseofthelocaloptimalsolution.Thegreedyalgorithmisnotabletoobtaintheglobaloptimalsolutionforallproblems,butforawiderangeofproblems,hecanproducetheglobaloptimalsolutionortheapproximatesolutionoftheglobaloptimalsolution.Thispapermainlyintroducesthecoreofthegreedyalgorithm,thecharacteristicsandtheexistingproblemsofthealgorithmitself..Keywords：greedyalgorithm;optimalsolution;knapsackproblem;0引言，為了解決各種實(shí)際問(wèn)題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪心策略等一紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)個(gè)好的算求解算法更像是一門(mén)藝術(shù)而不是像技術(shù)，但仍存在一些行之有效的、能夠用于解決許質(zhì)和貪心選擇性質(zhì)時(shí)，貪心算法通常給出一個(gè)簡(jiǎn)單，直觀和高效的解法。貪心算法通過(guò)一系列的選擇來(lái)得到一且每次貪心選擇都能將問(wèn)題化簡(jiǎn)為一個(gè)更小的與許多問(wèn)題不能總是產(chǎn)生整體最優(yōu)解，但對(duì)諸如最構(gòu)和貪心選擇性質(zhì)的問(wèn)題卻可以獲得整體最優(yōu)方法。其核心后將這多個(gè)輸所要求的順序，按這種順序當(dāng)前已構(gòu)成在解加在一起不能產(chǎn)生部分解中。這下最優(yōu)解的分級(jí)處理方，往往可能有好幾種量度標(biāo)準(zhǔn)似乎都是可取不是問(wèn)題的擇能產(chǎn)生問(wèn)題最并不是一件最優(yōu)量度標(biāo)準(zhǔn)效。最優(yōu)解可以通貪心選擇來(lái)達(dá)到，根這個(gè)選擇后產(chǎn)生子問(wèn)題，最終可得到問(wèn)本思想始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個(gè)算法中的某一步不能再繼續(xù)前進(jìn)。貪心算法的思想本質(zhì)就是分治，就是每次都處理處一個(gè)最好的方案。的核心貪心算法的核心問(wèn)題是選擇能生產(chǎn)最優(yōu)解的貪心策略是指從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的便可看出，貪心策略總是做出在當(dāng)前看來(lái)是最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問(wèn)題的自身的特性決定論該問(wèn)題法特性貪心算法可解決的問(wèn)題通常大部分都有如下有一個(gè)候選的對(duì)象的集合:比包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另。函數(shù)一樣，婪算法一步對(duì)象的集合函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。到集合里。每一次都。如果貪婪貪心算法的理論基礎(chǔ)-擬陣貪心策略是最接近人類(lèi)認(rèn)知思維的一種解題“擬陣”理論是一種能夠確定貪心策略何時(shí)(S,I):(1)S是非空有限集；(2)I是S的一類(lèi)具有遺傳性質(zhì)的獨(dú)立子集I滿足交換性質(zhì)，即若A∈I，B∈I，且引理(擬陣的貪心選擇性質(zhì))設(shè)M=(S,I)是引理(擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì))設(shè)x是求帶MSI的最優(yōu)子集的貪心算法Greedy化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問(wèn)題。定理(帶權(quán)擬陣貪心算法的正確性)高M(jìn)=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法Greedy結(jié)的問(wèn)題，即給定一個(gè)加權(quán)擬陣M=(S,I)，若能找題，只求解。擬陣一復(fù)雜優(yōu)缺點(diǎn)貪心算法是一種重要的算法設(shè)計(jì)策略而且其效率高。貪心算法并不從整體最優(yōu)考慮他所做出的選擇只是在某種意義上的局部最優(yōu)選擇，即在選擇導(dǎo)致最終結(jié)果是問(wèn)題的一個(gè)最優(yōu)解。貪心算法具有良好的爬坡能力，一般情況下該算法都可當(dāng)算法不能在限定的時(shí)間內(nèi)給，找滿足問(wèn)題要求的近似最優(yōu)解時(shí)，給出一個(gè)可行解及其計(jì)算誤差，作為決策參考。但隨著問(wèn)題規(guī)模和復(fù)雜的不斷提升，單一的算法在其收斂性和求解速度等方面已經(jīng)表現(xiàn)出的局限性，即使貪心算法的效率很只適用于少量實(shí)例。貪心算法解決問(wèn)題，也就是，以此類(lèi)多少。以是一。題的(無(wú)法被證明)的，解釋如下：最大者。020最小。它的反例與第重量?jī)r(jià)值最大的物282010重量?jī)r(jià)值一樣，程分割為任意大小，那么策最大的物品這個(gè)策規(guī)