※ 引述《kc655039 (NNN  )》之銘言：
: ※ 引述《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)