我現在在想這題,書上(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的習題,然後我想
練習這部分這樣.
大家有時間的話幫忙想一想好嗎謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.161.14.129