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