→ aaaaajack : 你想一下背包的dp在幹麻 這題其實還比原版背包簡單 10/16 05:31
→ aaaaajack : 時間=價值 分數=重量 10/16 05:32
→ mantour : 總分是目標分數以上就可以還是要剛好等於？ 10/16 09:17
→ cornerstone : 總分要剛好等於目標，否則就回傳-1 10/16 10:18
→ cornerstone : 我有想到分數=背包問題的重量，但背包內物品的價值 10/16 10:19
→ cornerstone : 要越高越好，而這題時間要越短越好，所以思路還是卡 10/16 10:21
→ cornerstone : 住，不過也有可能我沒有真正融會貫通背包問題 10/16 10:22
推 deathcustom : 1. 效率高的先挑 2. 同效率的時間長的先挑 10/16 10:27
→ deathcustom : e_k = p_k/t_k, 把e_k排序後來(不一定是最佳解 10/16 10:28
推 arrenwu : 你的這些 t 和 p 值都是正整數嗎？ 10/16 10:48
推 arrenwu : 然後菜看起來不可以重複做？ 10/16 10:51
→ arrenwu : 我看到菜只能選擇煮或不煮了 10/16 10:54
→ cornerstone : 抱歉，我題目沒寫清楚，都是正整數，菜不能重複煮 10/16 11:08
→ cornerstone : 我是在思路的部分有寫到因為不能重複煮，所以換錢 10/16 11:09
→ cornerstone : 換銅板的方式就不能應用到這題 10/16 11:10
→ mantour : 把菜依所需時間從小到大排序。從時間最短的菜當第 10/16 11:34
→ mantour : 一層，每道菜可做可不做，形成一個樹，用BFS遍歷每 10/16 11:34
→ mantour : 個節點的總分和時間，下一層節點的總分和時間可以 10/16 11:34
→ mantour : 用上一層的結果算。找出最淺層總分等於目標的節點 10/16 11:34
→ mantour : ，如果同一層有不只一個節點總分符合就取總時間最 10/16 11:34
→ mantour : 小的。如果都沒找到就回傳-1。 10/16 11:34
→ mantour : 總分超過目標的節點底下的分支就可以跳過不用算 10/16 11:36
→ mantour : 不過這樣好像有點笨 再想一下 10/16 11:41
→ cornerstone : 謝謝每一位的回覆，我會再想想！沒想過用樹的方式 10/16 12:09
→ cornerstone : 從大家的討論真的學到不同的思維...謝謝 10/16 12:10
→ mantour : 發現我的方法沒辦法保證第一個找到的就是時間最短 10/16 13:30
→ mantour : 的 10/16 13:30