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

※ 引述《cornerstone (cornerstone)》之銘言： : 標題: [其他] 一題演算法的問題 : 時間: Tue Oct 15 23:14:54 2024 : : 板上朋友們好， : 想要請教各位一題演算法的問題， : 題目大概是是說： : 有廚師參加一個烹飪比賽，大會給了一個目標分數g， : 有1~n道菜，每一道菜有特定的分數p，和所需要花費的時間t : 每個廚師可以自己選擇這道菜要煮還是不煮， : 請問廚師們要用怎麼樣的策略才能在最短的時間內湊到目標分數？ : 如果這些菜的分數無法剛剛好湊到目標分數，就回傳-1 : : 我看到這題目時，第一個想法是像是動態規劃的0/1背包問題 : （背包有重量限制，每個物品有各自的重量和價值， : 要在背包重量內塞進價值最高的物品） : : 所以目標分數就像是背包的重量， : 每一道菜可以選擇做或不做， : 就很像要不要把某個物件裝進背包中 : 但因為背包問題不需要考慮最少的物件， : 也不需要讓重量湊到剛好背包的容量... : 所以好像無法直接套用這樣的解題方式 : : 所以就改為或許可以用換銅板問題的思路去解， : 因為就是要用最少的銅板湊到需要找的錢 : 就像是題目中用最少的時間，湊到目標點數 : 但是因為換銅板的題目，各種幣值是可以重複用， : 而這個問題是每一道菜只能選擇煮或不煮 : 不能煮重複的菜 : : 想了一陣子，覺得好像有點方向，也覺得應該是動態規劃， : 可是好像無法真正釐清到底開如何解.... : 不知道有沒有人可以幫忙看看這題思路該怎麼想... : 或是有哪些類似題目可以參考？ : 謝謝大家！ 所以這問題看起來是給定下列數據： 正整數數列 times：代表每一道菜需要花的時間 正整數數列 points：代表每一道菜能得到的點數 正整數 g：需要的點數 "不能煮重複的菜" 看起來非常像是用 backtracking 的手法 分類應該是 Depth First Search 第一步先重新排序 times 和 points， 讓 points 的內容由小到大 菜品總共 n 樣，編號是從 0 ~ n-1. (Java Code) // 宣告一個廣域變數，用來儲存滿足分數所花費的最小時間 int result = Integer.MAX_VALUE int n = points.length // 這個函數會找尋在已經花了 currTime 的時間後， // 只做前面 0~ind 道菜且能達到 targetPoints 的情況下， // 所能找到的最小時間組合 void seek(int ind, int currTime, int targetPoints) { // 分數湊齊了 if (neededPoints == 0 ){ result = Math.min(result, currTime) } // 因為points有經過排序，所以直接跳到沒有比 targetPoints大的菜 while (ind> 0 && points[ind] > targetPoints) {ind--;} // 沒菜可以做了 if(ind < 0){ return;} // 選擇做第ind道菜的情況 seek(ind-1, currTime+times[ind], targetPoints - points[ind]); // 選擇不做第ind道菜的情況 seek(ind-1, currTime, targetPoints); } // 找尋最小時間 int main() { seek(n-1, 0, g); if (result < Integer.MAX_VALUE) { return result; } else { return -1; } } -- 角卷綿芽給予炭治郎的建議 https://i.imgur.com/0mPdESk.jpg https://i.imgur.com/Ts4dBjy.jpg -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.195.96 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1729049316.A.BD8.html