【题解】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<