簡單背包問題專題

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

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

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