作者cornerstone (cornerstone)
看板Math
標題[其他] 一題演算法的問題
時間Tue Oct 15 23:14:54 2024
板上朋友們好，
想要請教各位一題演算法的問題，
題目大概是是說：
有廚師參加一個烹飪比賽，大會給了一個目標分數g，
有1~n道菜，每一道菜有特定的分數p，和所需要花費的時間t
每個廚師可以自己選擇這道菜要煮還是不煮，
請問廚師們要用怎麼樣的策略才能在最短的時間內湊到目標分數？
如果這些菜的分數無法剛剛好湊到目標分數，就回傳-1
我看到這題目時，第一個想法是像是動態規劃的0/1背包問題
（背包有重量限制，每個物品有各自的重量和價值，
要在背包重量內塞進價值最高的物品）
所以目標分數就像是背包的重量，
每一道菜可以選擇做或不做，
就很像要不要把某個物件裝進背包中
但因為背包問題不需要考慮最少的物件，
也不需要讓重量湊到剛好背包的容量...
所以好像無法直接套用這樣的解題方式
所以就改為或許可以用換銅板問題的思路去解，
因為就是要用最少的銅板湊到需要找的錢
就像是題目中用最少的時間，湊到目標點數
但是因為換銅板的題目，各種幣值是可以重複用，
而這個問題是每一道菜只能選擇煮或不煮
不能煮重複的菜
想了一陣子，覺得好像有點方向，也覺得應該是動態規劃，
可是好像無法真正釐清到底開如何解....
不知道有沒有人可以幫忙看看這題思路該怎麼想...
或是有哪些類似題目可以參考？
謝謝大家！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.209.77.104 (美國)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1729005296.A.A8D.html
1F：→ aaaaajack : 你想一下背包的dp在幹麻 這題其實還比原版背包簡單 10/16 05:31
2F：→ aaaaajack : 時間=價值 分數=重量 10/16 05:32
3F：→ mantour : 總分是目標分數以上就可以還是要剛好等於？ 10/16 09:17
4F：→ cornerstone : 總分要剛好等於目標，否則就回傳-1 10/16 10:18
5F：→ cornerstone : 我有想到分數=背包問題的重量，但背包內物品的價值 10/16 10:19
6F：→ cornerstone : 要越高越好，而這題時間要越短越好，所以思路還是卡 10/16 10:21
7F：→ cornerstone : 住，不過也有可能我沒有真正融會貫通背包問題 10/16 10:22
8F：推 deathcustom : 1. 效率高的先挑 2. 同效率的時間長的先挑 10/16 10:27
9F：→ deathcustom : e_k = p_k/t_k, 把e_k排序後來(不一定是最佳解 10/16 10:28
10F：推 arrenwu : 你的這些 t 和 p 值都是正整數嗎？ 10/16 10:48
11F：推 arrenwu : 然後菜看起來不可以重複做？ 10/16 10:51
12F：→ arrenwu : 我看到菜只能選擇煮或不煮了 10/16 10:54
13F：→ cornerstone : 抱歉，我題目沒寫清楚，都是正整數，菜不能重複煮 10/16 11:08
14F：→ cornerstone : 我是在思路的部分有寫到因為不能重複煮，所以換錢 10/16 11:09
15F：→ cornerstone : 換銅板的方式就不能應用到這題 10/16 11:10
16F：→ mantour : 把菜依所需時間從小到大排序。從時間最短的菜當第 10/16 11:34
17F：→ mantour : 一層，每道菜可做可不做，形成一個樹，用BFS遍歷每 10/16 11:34
18F：→ mantour : 個節點的總分和時間，下一層節點的總分和時間可以 10/16 11:34
19F：→ mantour : 用上一層的結果算。找出最淺層總分等於目標的節點 10/16 11:34
20F：→ mantour : ，如果同一層有不只一個節點總分符合就取總時間最 10/16 11:34
21F：→ mantour : 小的。如果都沒找到就回傳-1。 10/16 11:34
22F：→ mantour : 總分超過目標的節點底下的分支就可以跳過不用算 10/16 11:36
23F：→ mantour : 不過這樣好像有點笨 再想一下 10/16 11:41
24F：→ cornerstone : 謝謝每一位的回覆，我會再想想！沒想過用樹的方式 10/16 12:09
25F：→ cornerstone : 從大家的討論真的學到不同的思維...謝謝 10/16 12:10
26F：→ mantour : 發現我的方法沒辦法保證第一個找到的就是時間最短 10/16 13:30
27F：→ mantour : 的 10/16 13:30