The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

導(dǎo)航

<

2010年1月

>

日

一

二

三

四

五

六

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

搜索

閱讀排行榜

評論排行榜

POJ 1837-Balance 0/1背包問題的擴(kuò)展

//copyright by abilitytao

#include <iostream>

using namespace std;

int pos[21];

int weight[21];

int mid=4000;

int result[21][8000];

int c,g;

int main()

{

int i,j,k;

scanf("%d%d",&c,&g);

for(i=1;i<=c;i++)

scanf("%d",&pos[i]);

for(i=1;i<=g;i++)

scanf("%d",&weight[i]);

for(i=1;i<=c;i++)

{

result[1][pos[i]*weight[1]+4000]++;

}

// 以上是dp初始化,接下來將用動(dòng)態(tài)規(guī)劃不斷地掛上新的砝碼；

for(i=2;i<=g;i++)

{

for(j=1;j<=c;j++)

for(k=1;k<=8000;k++)

{

if(result[i-1][k]!=0)

result[i][k+weight[i]*pos[j]]+=result[i-1][k];

}

printf("%d\n",result[g][4000]);

return 0;

}

這個(gè)題目做的確實(shí)有點(diǎn)郁悶，說實(shí)話，我是參考網(wǎng)上的代碼做的，即使如此，我還是沒法證明那個(gè)狀態(tài)轉(zhuǎn)移方程的正確性；
只是感覺上像是對的，汗~后來聯(lián)想到弗洛伊德和bellman-ford我這樣說了：一切盡在迭代中啊~
如果有牛人能幫我證明一下的話我感激不盡呵＆我的qq:64076241

再說說做這個(gè)題目的收獲，那個(gè)+4000的小技巧倒是很受用，呵呵；
還有就是對動(dòng)態(tài)規(guī)劃的感覺越來越好了，有的時(shí)候能憑直覺把題做出來了...

posted on 2009-02-20 00:03 abilitytao 閱讀(1663) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品