動(dòng)態(tài)規(guī)劃經(jīng)典教程——背包問題的拓展

2.4 背包問題的拓展

前面說的背包問題還有個(gè)有趣的變形，可以說是背包問題的拓展吧，下面看一下這個(gè)例題：

例題20   找啊找啊找GF   (gf.pas/c/cpp)   來源：MM群2007七夕模擬賽（RQNOJ 57）

【問題描述】

"找啊找啊找GF,找到一個(gè)好GF,吃頓飯啊拉拉手,你是我的好GF.再見."

"誒,別再見啊..."

七夕...七夕...七夕這個(gè)日子,對于sqybi這種單身的菜鳥來說是多么的痛苦...雖然他聽著這首叫做"找啊找啊找GF"的歌,他還是很痛苦.為了避免這種痛苦,sqybi決定要給自己找點(diǎn)事情干.他去找到了七夕模擬賽的負(fù)責(zé)人zmc MM,讓她給自己一個(gè)出題的任務(wù).經(jīng)過幾天的死纏爛打,zmc MM終于同意了.

但是,拿到這個(gè)任務(wù)的sqybi發(fā)現(xiàn),原來出題比單身更讓人感到無聊-_-....所以,他決定了,要在出題的同時(shí)去辦另一件能夠使自己不無聊的事情--給自己找GF.

sqybi現(xiàn)在看中了n個(gè)MM,我們不妨把她們編號1到n.請MM吃飯是要花錢的,我們假設(shè)請i號MM吃飯要花rmb[i]塊大洋.而希望騙MM當(dāng)自己GF是要費(fèi)人品的,我們假設(shè)請第i號MM吃飯?jiān)噲D讓她當(dāng)自己GF的行為(不妨稱作泡該MM)要耗費(fèi)rp[i]的人品.而對于每一個(gè)MM來說,sqybi都有一個(gè)對應(yīng)的搞定她的時(shí)間,對于第i個(gè)MM來說叫做time[i]. sqybi保證自己有足夠的魅力用time[i]的時(shí)間搞定第i個(gè)MM^_^.

sqybi希望搞到盡量多的MM當(dāng)自己的GF,這點(diǎn)是毋庸置疑的.但他不希望為此花費(fèi)太多的時(shí)間(畢竟七夕賽的題目還沒出),所以他希望在保證搞到MM數(shù)量最多的情況下花費(fèi)的總時(shí)間最少.

sqybi現(xiàn)在有m塊大洋,他也通過一段時(shí)間的努力攢到了r的人品(這次為模擬賽出題也攢rp哦~~).他憑借這些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花費(fèi)的最少時(shí)間是多少.

注意sqybi在一個(gè)時(shí)刻只能去泡一個(gè)MM--如果同時(shí)泡兩個(gè)或以上的MM的話,她們會(huì)打起來的...

【輸入文件】

輸入的第一行是n,表示sqybi看中的MM數(shù)量.

接下來有n行,依次表示編號為1, 2, 3, ..., n的一個(gè)MM的信息.每行表示一個(gè)MM的信息,有三個(gè)整數(shù):rmb, rp和time.

最后一行有兩個(gè)整數(shù),分別為m和r.

【輸出文件】

你只需要輸出一行,其中有一個(gè)整數(shù),表示sqybi在保證MM數(shù)量的情況下花費(fèi)的最少總時(shí)間是多少.

【輸入樣例】

4

1 2 5

2 1 6

2 2 2

2 2 3

5 5

【輸出樣例】

13

【數(shù)據(jù)規(guī)?！?/span>

對于20%數(shù)據(jù),1<=n<=10;

對于100%數(shù)據(jù),1<=rmb<=100,1<=rp<=100,1<=time<=1000;

對于100%數(shù)據(jù),1<=m<=100,1<=r<=100,1<=n<=100.

【提交鏈接】

http://www.rqnoj.cn/Submit.asp

【問題分析】

初看問題覺得條件太多，理不出頭緒來，所以要將問題簡化，看能否找出熟悉的模型來，如果我們只考慮錢夠不夠，或只考慮RP夠不夠。并且不考慮花費(fèi)的時(shí)間。這樣原問題可以簡化成下面的問題：

在給定M元RMB（或R單位RP，RP該用什么單位呢？汗。。。）的前題下，去泡足夠多的MM，很顯然這個(gè)問題就是典型的0/1背包問題了。

可以把泡MM用的RMB（或RP看做重量），泡到MM的個(gè)數(shù)看做價(jià)值，給定的M（或R）就是背包的載重。求解這個(gè)問題很輕松嘍。

但是，這個(gè)問題既要考慮RMB有要考慮RP怎么辦呢？

解決這個(gè)問題很容易啊，要是你有足夠的RMB去泡第i個(gè)MM而RP不夠就泡不成了，要是RP夠就可以。也就是在原來問題的基礎(chǔ)上在狀態(tài)加一維。

那要是在考慮上時(shí)間最小怎么辦呢？

這個(gè)也很好說，在求解過程中如果花X元RMP，Y單位RP可以到Z個(gè)MM，那么在泡第i個(gè)MM時(shí)，發(fā)現(xiàn)可以用X-rmb[i]元，Y-rp[i]單位RP泡到的MM數(shù)加上這個(gè)MM（也就是+1）比原來Z多，就替換它（因?yàn)槟愕脑瓌t是盡量多的泡MM），如果和Z一樣多，這是就要考慮原來花的時(shí)間多呢，還是現(xiàn)在花的時(shí)間多。要是原來的多，就把時(shí)間替換成現(xiàn)在用的時(shí)間（因?yàn)槟慵热豢梢耘莸较嗤瑪?shù)量的MM當(dāng)然要省點(diǎn)時(shí)間去出題）。

設(shè)計(jì)一個(gè)二維狀態(tài)opt[j,k]表示正好花j元RMP，k單位RP可以泡到的最多的MM的數(shù)量。增加一個(gè)輔助的狀態(tài)ct[k,j]表示正好花j元RMP，k單位RP可以泡到的最多MM的情況下花費(fèi)的最少的時(shí)間。

邊界條件 opt[0,0]=1    (按題意應(yīng)該是0，但為了標(biāo)記花費(fèi)是否正好設(shè)為1，這樣，opt[j,k]>0說明花費(fèi)正好)

狀態(tài)轉(zhuǎn)移方程：

opt[j,k]=max{opt[j-rmb[i],k-rp[i]]+1}

(rmb[i]<=j<=m,rp[i]<=k<=r,0<i<=n,opt[j-rmb[i],k-rp[i]]>0)

ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i]   (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1)

時(shí)間復(fù)雜度：

階段數(shù) O（N）*狀態(tài)數(shù)O（MR）*轉(zhuǎn)移代價(jià)O（1）=    O（NMR）

注：數(shù)據(jù)挺小的。

問題拓展：

如果要加入別的條件，比如泡MM還要一定的SP，等也就是說一個(gè)價(jià)值要不同的條件確定，那么這個(gè)問題的狀態(tài)就需要在加一維，多一個(gè)條件就多一維。

【源代碼】

program gf;

const

fin='gf.in';

fout='gf.out';

maxn=110;

var

rmb,rp,time:array[0..maxn] of longint;

opt,ct:array[0..maxn,0..maxn] of longint;

n,m,r,ans,max:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(n);

for i:=1 to n do

read(rmb[i],rp[i],time[i]);

read(m,r);

close(input);

end;

procedure main;

var

i,j,k:longint;

begin

fillchar(opt,sizeof(opt),0);

fillchar(ct,sizeof(ct),0);

opt[0,0]:=1;

for i:=1 to n do

for j:=m downto rmb[i] do

for k:=r downto rp[i] do

if opt[j-rmb[i],k-rp[i]]>0 then

begin

if opt[j-rmb[i],k-rp[i]]+1>opt[j,k] then

begin

opt[j,k]:=opt[j-rmb[i],k-rp[i]]+1;

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i];

end

else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k])

and (ct[j-rmb[i],k-rp[i]]+time[i]<ct[j,k]) then

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+time[i];

end;

max:=0;

for j:=1 to m do

for k:=1 to r do

if opt[j,k]>max then

begin

max:=opt[j,k];

ans:=ct[j,k];

end

else if (opt[j,k]=max) and (ct[j,k]<ans) then

ans:=ct[j,k];

end;

procedure print;

begin

writeln(ans);

close(output);

end;

begin

init;

main;

print;

end.