※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1729049316.A.BD8.html ※ 编辑: arrenwu (98.45.195.96 美国), 10/16/2024 11:29:34