N[i]中四個(gè)值,begin,end,p,vnow,五個(gè)值也行,value為=(end-begin)*p。
1,不剪枝也能過。
2,如果剪枝,
根據(jù)回溯的過程,會(huì)先求到dfs(n)最后那個(gè)結(jié)點(diǎn),再是dfs(n-1)..dfs(1)。
剪枝應(yīng)當(dāng)是在結(jié)構(gòu)體中N[i]增加一個(gè)變量vnow,
vnow初值為0,記錄從該結(jié)點(diǎn)開始搜索所有int dfs(i)的返回值,并不斷更新使其最大,
當(dāng)搜索到i的時(shí)候,如果N[i].vnow不為0,則需要滿足N[i].vnow+當(dāng)前temp(前面的可行系列的總值)>vmax(所要求的最大值的當(dāng)前值),若vnow為0,則可以不滿足這個(gè)條件,因?yàn)檫@是第一次。
根據(jù)回溯的過程,第一次求得的結(jié)果是dfs(n),接下來是dfs(n-1),接下來是dfs(n-2)-------最后dfs(0);
posted on 2009-07-25 22:27
luis 閱讀(264)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
搜索