簡(jiǎn)單背包問(wèn)題專(zhuān)題

1、簡(jiǎn)單背包問(wèn)題專(zhuān)題作者：爐灰本文內(nèi)容遵從CC版權(quán)協(xié)議一：01背包問(wèn)題例題：紀(jì)老師的減肥的減肥計(jì)劃話(huà)說(shuō)，一日我們親愛(ài)敬愛(ài)可愛(ài)的紀(jì)老師為了讓自己的體型更加完美，于是乎毅然決然的加入了減肥大軍的行列中來(lái)。他打算在n小時(shí)內(nèi)將自己的體重從w減到盡可能低。紀(jì)老師的減肥方法是不吃飯，而每個(gè)小時(shí)不吃飯所能減的體重并不相同。同樣老師因?yàn)椴怀远陆档膆p也不相同?，F(xiàn)在紀(jì)老師想讓你幫忙求出他的體重最低可以達(dá)到多少。（我想大家都不希望老師餓死吧^_^）輸入格式：

2、第一行有三個(gè)數(shù)，分別是n、w、HP。第二行到第n1行每行有兩個(gè)數(shù)，分別表示該小時(shí)不吃飯所減的體重wi和下降的hpi。每個(gè)數(shù)間用空格隔開(kāi)。輸出格式：輸出一個(gè)數(shù)，即老師可以達(dá)到的最低體重。樣例輸入：42001001490221090110399樣例輸出：164解析：此為典型的01背包問(wèn)題，hp是背包容量，下降體重wi是價(jià)值，而每個(gè)小時(shí)吃不吃飯則是該物品取不取。該類(lèi)問(wèn)題用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可

3、以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][j]=maxf[i1][j]f[i1][jhp[i]]w[i]。用遞推的f結(jié)構(gòu)實(shí)現(xiàn)出來(lái)如下，其中用f[i][j]表示在前i個(gè)小時(shí)有j點(diǎn)hp所能減的最大體重。f(i=1i=0j)j表示在前i個(gè)小時(shí)還有j點(diǎn)hp時(shí)if(f[i1][j]f[i1][jhp[i]]w[i])比較是吃還是不吃是最優(yōu)f[i][j]=f[i1][j]不吃的時(shí)候體重不變elsef[i][j]=f[i1][jhp[i]]w