※ 引述《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)