計算所有箱子的承載重量總和,並且將物品進行排序。將物品依序相加並且判斷是否會超過最大承載量,如果會的話就停止迴圈,並且要紀錄目前相加到第幾樣商品。
宣告一個回傳值為 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。