[其他] 一題演算法的問題

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