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) 編輯 收藏 引用 所屬分類:
搜索