作者cornerstone (cornerstone)
看板Math
标题[其他] 一题演算法的问题
时间Tue Oct 15 23:14:54 2024
板上朋友们好，
想要请教各位一题演算法的问题，
题目大概是是说：
有厨师参加一个烹饪比赛，大会给了一个目标分数g，
有1~n道菜，每一道菜有特定的分数p，和所需要花费的时间t
每个厨师可以自己选择这道菜要煮还是不煮，
请问厨师们要用怎麽样的策略才能在最短的时间内凑到目标分数？
如果这些菜的分数无法刚刚好凑到目标分数，就回传-1
我看到这题目时，第一个想法是像是动态规划的0/1背包问题
（背包有重量限制，每个物品有各自的重量和价值，
要在背包重量内塞进价值最高的物品）
所以目标分数就像是背包的重量，
每一道菜可以选择做或不做，
就很像要不要把某个物件装进背包中
但因为背包问题不需要考虑最少的物件，
也不需要让重量凑到刚好背包的容量...
所以好像无法直接套用这样的解题方式
所以就改为或许可以用换铜板问题的思路去解，
因为就是要用最少的铜板凑到需要找的钱
就像是题目中用最少的时间，凑到目标点数
但是因为换铜板的题目，各种币值是可以重复用，
而这个问题是每一道菜只能选择煮或不煮
不能煮重复的菜
想了一阵子，觉得好像有点方向，也觉得应该是动态规划，
可是好像无法真正厘清到底开如何解....
不知道有没有人可以帮忙看看这题思路该怎麽想...
或是有哪些类似题目可以参考？
谢谢大家！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 71.209.77.104 (美国)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1729005296.A.A8D.html
1F：→ aaaaajack : 你想一下背包的dp在干麻 这题其实还比原版背包简单 10/16 05:31
2F：→ aaaaajack : 时间=价值 分数=重量 10/16 05:32
3F：→ mantour : 总分是目标分数以上就可以还是要刚好等於？ 10/16 09:17
4F：→ cornerstone : 总分要刚好等於目标，否则就回传-1 10/16 10:18
5F：→ cornerstone : 我有想到分数=背包问题的重量，但背包内物品的价值 10/16 10:19
6F：→ cornerstone : 要越高越好，而这题时间要越短越好，所以思路还是卡 10/16 10:21
7F：→ cornerstone : 住，不过也有可能我没有真正融会贯通背包问题 10/16 10:22
8F：推 deathcustom : 1. 效率高的先挑 2. 同效率的时间长的先挑 10/16 10:27
9F：→ deathcustom : e_k = p_k/t_k, 把e_k排序後来(不一定是最佳解 10/16 10:28
10F：推 arrenwu : 你的这些 t 和 p 值都是正整数吗？ 10/16 10:48
11F：推 arrenwu : 然後菜看起来不可以重复做？ 10/16 10:51
12F：→ arrenwu : 我看到菜只能选择煮或不煮了 10/16 10:54
13F：→ cornerstone : 抱歉，我题目没写清楚，都是正整数，菜不能重复煮 10/16 11:08
14F：→ cornerstone : 我是在思路的部分有写到因为不能重复煮，所以换钱 10/16 11:09
15F：→ cornerstone : 换铜板的方式就不能应用到这题 10/16 11:10
16F：→ mantour : 把菜依所需时间从小到大排序。从时间最短的菜当第 10/16 11:34
17F：→ mantour : 一层，每道菜可做可不做，形成一个树，用BFS遍历每 10/16 11:34
18F：→ mantour : 个节点的总分和时间，下一层节点的总分和时间可以 10/16 11:34
19F：→ mantour : 用上一层的结果算。找出最浅层总分等於目标的节点 10/16 11:34
20F：→ mantour : ，如果同一层有不只一个节点总分符合就取总时间最 10/16 11:34
21F：→ mantour : 小的。如果都没找到就回传-1。 10/16 11:34
22F：→ mantour : 总分超过目标的节点底下的分支就可以跳过不用算 10/16 11:36
23F：→ mantour : 不过这样好像有点笨 再想一下 10/16 11:41
24F：→ cornerstone : 谢谢每一位的回覆，我会再想想！没想过用树的方式 10/16 12:09
25F：→ cornerstone : 从大家的讨论真的学到不同的思维...谢谢 10/16 12:10
26F：→ mantour : 发现我的方法没办法保证第一个找到的就是时间最短 10/16 13:30
27F：→ mantour : 的 10/16 13:30