#41597: C++詳解-DFS


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-10-28 09:54:40
a455. TOI2010 第四題:商品特賣問題 -- 2010TOI研習營初選 | From: [24.147.249.5] | 發表日期 : 2024-08-09 12:08

計算所有箱子的承載重量總和,並且將物品進行排序。將物品依序相加並且判斷是否會超過最大承載量,如果會的話就停止迴圈,並且要紀錄目前相加到第幾樣商品。

宣告一個回傳值為 bool 的 DFS,並且預設參數為兩個 int,分別為 num 和 box,代表目前要拿的物品序列號和要從哪一個箱子開始進行判斷。

在 DFS 中,對所有箱子進行判斷,如果目前的 num 商品塞得下這個箱子,則將商品塞到這個箱子看看,並且再次呼叫 DFS,只是這次 num 要 -1,並且 box 要使用 i,也就是目前跑到的箱子編號。如果這個 DFS 回傳值為 true,則可以在還原剛剛塞的商品後直接 return true。

如果呼叫 DFS 時發現 num < 0,代表已經把所有商品都判斷過了,就可以 return true。然後,要宣告一個 int start = 0,如果 box > 0 && items[num] == items[num+1],代表目前商品和上一個商品大小一樣且已經有判斷過商品了,就將 start 設為 box,並且在判斷所有箱子時,將 For迴圈 的起點改成 start。

跑一個從 0 到 N-1 的 For迴圈,並且判斷 DFS(i+1, 0) 是否為 true,如果不成立就將迴圈 break,答案就是 i+1。

 

範例程式碼

 
ZeroJudge Forum