※ 引述《kc655039 (￾NN￾N ￾  )》之銘言： : 我現在在想這題,書上(programming challenge)有個提示,說: : The potential size of this problem makes it a challenge , : perhaps too large for backtracking even with sophisticated pruning. : Can we keep track of all team weights realizable by some : subset of the first i people, without explicitly enumerating : the 2^i subsets? Note that the number of distinct possible team weights : is much smaller than 2^i. : 紅色字的涵義我想不懂,有人可以提示我一下下嗎, : 如果有四人,那一定是兩人兩人一隊,然後去用backtracking, : 累加到到兩個人為止,然後在比較兩對體重的差距,如果比較小, : 就把紀錄換成目前的兩對體重,可是如果有一百人(上限), : 而且都沒有同體重的人,那可能要跑100P50?. : 照我這樣做的話一定會TLE的. : 要用backtracking的原因是,這個題目是backtracking的習題,然後我想 : 練習這部分這樣. : 大家有時間的話幫忙想一想好嗎謝謝 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.) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.250.175