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

板上朋友們好， 想要請教各位一題演算法的問題， 題目大概是是說： 有廚師參加一個烹飪比賽，大會給了一個目標分數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