【题解】google code jam 程序竞赛 Round1-A 第二题

之前看到有大大在分享qualify round的题目
想说也来分享一下round1的题目和题解~

google code jam是每年一次的google纪念衣争夺战!
在Round2拿到全世界前1000名的人都可以拿到一件使你走路有风的google衬衫>w<

Round1分成三个sub round,每次取1000个人晋级
上周的roundA能否晋级的分界线就差不多在于第二题的大测有没有解出来
因此跟大家分享一下第二题的作法~

连结:
https://code.google.com/codejam/contest/5304486/dashboard#s=p1

题目:
给予一个料理的食谱,此料理由N种食材组合而成。
给予R1 R2 … RN,代表一份料理每一种食材所需要的分量(公克)
现在你每一种食材都有P包,每一包的重量都不尽相同
将这N种食材各取1包,可以组合成一个制作K份料理的大补帖,只要每包的重量都是所需份量的K * 0.9倍至K * 1.1倍之间,就是合法的组合
请问最多可以包成几包大补帖?

做法:

  • 每一包食材包,找出他所对应的份数的区间,例如洋葱一份70克,那么1500克的洋葱可以当成20份、21份、22份、23份
  • 将同种类的材料包依照重量大小排序好
  • 选一种食材当起始点,对于其他食材做搜索,能选小包就尽量小包,每次选择都会缩小可行区间,若再也没有符合的选择,则回溯到上一层选较大包的
  • 记得用一个boolean阵列纪录该包食材是否已经在上一次包大补帖用掉了
  • 看起来像DFS,但因为每次都能够快速决定是否合法,因此复杂度能保证在P * N左右

希望有帮到人唷>W<