[理工] 一題演算法的問題已刪文
想要請教各位一題演算法的問題，
題目大概是是說：
廚師參加一個烹飪比賽，大會給了一個目標分數g，
有1~n道菜，每一道菜有特定的分數p，和所需要花費的時間t
請問要怎麼樣在最短的時間湊到目標分數？
如果無法剛剛好湊到這個目標分數，就回傳-1
我看到這題目時，第一個想法是像是動態規劃的背包問題
目標分數就是背包的重量，
每一道菜可以選擇做或不做，
就很像要不要把某個物件裝進背包中
但因為背包問題不需要考慮最少的物件...所以就覺得可能不適用
想到或許可以用換銅板問題的思路去解，
因為就是要用最少的銅板湊到需要找的錢
但是因為銅板是可以重複用，但這個是每一道菜只能選擇煮或不煮
不能煮重複的菜
感覺題目不難，也覺得應該是動態規劃，
可是整個就卡住，不知道該怎麼想....
不知道有沒有人可以幫忙看看這題思路該怎麼想...
或是有沒有類似題目可以參考
謝謝大家！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.209.89.17 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1728959105.A.E8A.html