※ 引述《kc655039 (￾NN￾N ￾  )》之銘言： : ※ 引述《sophialiege (別忘了)》之銘言： : : I think the author means the "memorized search". : : "A table to memorize some useful information at each level(maybe can be : : reduced into fewer ones, it depends) you search; then based on the : : information you can cut the tree into a far smaller one." : : The main idea of Dynamic Programming is something like that. : : (You can find what DP is at almost all algorithm books.) : : Finally, the quickest way to solve this problem is greedy method. : : (You can also find that at almost all algorithm books.) : 我還是想不出來怎麼用不拖泥帶水的backtracking在這題上面, : 書上的提示老實講,我現在還是看不懂, : 一定是有某種方法我完完全全沒有想到才會這樣, : 所以如果有人知道怎麼做麻煩說明一下吧..... There are many approaching methods, I only show a possible one. 1 2 3 ...... 0 [*][ ][ ] 1 [ ][ ][*] 2 [*][ ][ ] 3 [ ][ ][ ] . . . It's a two dimension array, * means on, blank means off. If the grid[a][b] is on means we can construct weight a with b people. Look at the picture above, grid[0][1] is on means we can construct weight 0 with 1 people, and so on. If we maintain this kind table when searching, we can eliminate something without necessary need. For instance, if we use first c people to let grid[a][b] on. Should we try using first d(d>c) people to let grid[a][b] on again? Why or why not? If you have some books discussing DP algorithm, it will be very helpful to understand that. Good luck. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.250.175 ※ 編輯: sophialiege 來自: 140.112.250.175 (02/26 00:43)