Week3 - 挑戰題：貪婪的小偷 Part2

這題我猜應該要用 BFS 或 DFS 來解
但 Google 查到的主要有暴力破解跟動態規劃兩種解法
沒有人提到 BFS 或 DFS，那就先自己寫看看暴力破解吧

暴力破解：

1. 每個物品只考慮拿或不拿
2. 找出所有可能的組合，再過濾重量超過條件的
3. 剩下的都是符合條件的組合，再從中找出最高的價值回傳

寫完放上 LIOJ 後，又是 Time Limit Exceeded，可惡，說好的放心暴力破解呢 XD
難道我比系統預期的更粗魯的解了這題嗎

Update Log

1. 更早的檢查是否超過重量
   在要放進背包前就先檢查重量，減少不必要的運算
   結果還是 Time Limit Exceeded
2. 更早的檢查是否為最高價值
   把最高價值存在 bestResult，預設為 0
   在每次的組合完成時，順便把這個組合跟目前最高的價值比較，較大則更新最高價值
   結果還是 Time Limit Exceeded

翻更多文章後，意外看到應該是上一期學長的文章，
用的方法跟我很像，而且也遇到 Time Limit Exceeded 的問題
huli 有留言說就算迴圈全部只留下有用 i.toString(2).padStart(n, '0') 的這行，也會 Time Limit Exceeded
我猜應該是 toString() 其實需要做很多事情，所以效率不高
那就想別的方法吧！

看了學長的文章
試著用他的方法寫了自己的版本，放到 LIOJ，結果 Wrong Answer
Hmmm......應該不算太壞的消息吧.......
搞不好又是資料型態的問題
繼續燒腦

終於在睡前找到原因了！
我原本覺得不需要處理物品重量超過背包限重的情況
沒想到這就是我致命的失誤

物品重量超過背包重量，要直接沿用上一次的最佳解

雖然還想不到為什麼會需要這樣處理
不過我決定留給明天的我去研究！