s*********s
发帖数: 318 | 1 SF某startup coding test题
假设一个文件里包括某城所有餐馆的菜名和价钱。格式是 餐馆ID，价钱，菜名(包括
combo)。
1， 7.50， a
1, 12.50, a, b
1, 5.00, c
2, 8.00, a
2, 5.00, b
2, 9.00, b, d
程序要求：给定一个order, 输出最便宜的餐馆ID和总价。
order: a b, 输出 1 12.50
order: e, 输出 null
order: d, 输出 2 9.00 | r*******e
发帖数: 7583 | 2 只能想到brute-force的
把菜单做成一个菜或者combo做index的hashmap
对于order
求 all partitions of a set (including crossing partitions)
然后对每个partition求总价
【在 s*********s 的大作中提到】
: SF某startup coding test题
: 假设一个文件里包括某城所有餐馆的菜名和价钱。格式是 餐馆ID，价钱，菜名(包括
: combo)。
: 1， 7.50， a
: 1, 12.50, a, b
: 1, 5.00, c
: 2, 8.00, a
: 2, 5.00, b
: 2, 9.00, b, d
: 程序要求：给定一个order, 输出最便宜的餐馆ID和总价。
| s*********s
发帖数: 318 | 3 我也只能想到brute-force。order本身可能有duplicates: a b a c | s******s
发帖数: 31 | 4 可不可以从不同餐馆order？多order？有combo就要用dp吧。这道和usaco 3.3
shopping offers大同小异。如果可以多order，并且
要输出餐馆id的话，会稍麻烦点。 | s*********s
发帖数: 318 | 5 只能选一家最便宜的餐馆。
如果有DP思路的话，详细说说。
【在 s******s 的大作中提到】
: 可不可以从不同餐馆order？多order？有combo就要用dp吧。这道和usaco 3.3
: shopping offers大同小异。如果可以多order，并且
: 要输出餐馆id的话，会稍麻烦点。
| s******s
发帖数: 31 | 6 个人看法，每个餐馆都用dp算最便宜的买法。就是n-d weighted knapsnack。如果一共
有n种菜，那建立一个n-dimensional matrix。每个dimension对应一道菜。每个
dimension的index是一道菜的数量。matrix的值是能买到的最低的价格。与一般
knapsack不同之处是需要处理多买的情况。今天没时间写code，你可以先看看类似的题
，希望对你有帮助。 | p*****2
发帖数: 21240 | 7 combo没看懂
2, 9.00, b, d
order: d, 输出 2 9.00
只order d的话为什么跟combo一个价钱呢？ | s*********s
发帖数: 318 | 8 因为只有那个combo含d.
【在 p*****2 的大作中提到】
: combo没看懂
: 2, 9.00, b, d
: order: d, 输出 2 9.00
: 只order d的话为什么跟combo一个价钱呢？
| p*****2
发帖数: 21240 | 9
为什么不return null呢？
感觉更make sense。
【在 s*********s 的大作中提到】
: 因为只有那个combo含d.
| s*********s
发帖数: 318 | 10 题目要求，可以多order.
【在 p*****2 的大作中提到】
:
: 为什么不return null呢？
: 感觉更make sense。
| | | p*****2
发帖数: 21240 | 11
多order可以。我的意思是我要order一个d，结果你给我送来个combo就不对了吧。系统
可以提示不能这么order更合理吧。
【在 s*********s 的大作中提到】
: 题目要求，可以多order.
| s*********s
发帖数: 318 | 12 不管合不合理，这个题目要求输出含d的餐馆id.
【在 p*****2 的大作中提到】
:
: 多order可以。我的意思是我要order一个d，结果你给我送来个combo就不对了吧。系统
: 可以提示不能这么order更合理吧。
| p*****2
发帖数: 21240 | 13
1， 7.50， a
1, 12.50, a, b
1, 5.00, c
2, 8.00, a
2, 5.00, b
2, 9.00, b, d
order可以随便下吧？比如a,b,d
【在 s*********s 的大作中提到】
: 不管合不合理，这个题目要求输出含d的餐馆id.
| s*********s
发帖数: 318 | 14 是啊。如果是input_data，return因该是：
2 17.00
【在 p*****2 的大作中提到】
:
: 1， 7.50， a
: 1, 12.50, a, b
: 1, 5.00, c
: 2, 8.00, a
: 2, 5.00, b
: 2, 9.00, b, d
: order可以随便下吧？比如a,b,d
| p*****2
发帖数: 21240 | 15
结果必须是一个饭店，还是可以几个饭店混合呀？
【在 s*********s 的大作中提到】
: 是啊。如果是input_data，return因该是：
: 2 17.00
| s*********s
发帖数: 318 | | p*****2
发帖数: 21240 | 17
如果一个饭店menu不全，就返回null了吧？
【在 s*********s 的大作中提到】
: 必须是一个饭店
| h**6
发帖数: 4160 | | s*********s
发帖数: 318 | 19 是的
【在 p*****2 的大作中提到】
:
: 如果一个饭店menu不全，就返回null了吧？
| s*********s
发帖数: 318 | 20 写了个brute-force。总觉得不应该是这样。 | | | p*****2
发帖数: 21240 | 21
可以一个饭店一个饭店的算。算一个饭店就算bruteforce的话也是很快的。一个饭店的
menu实在是有限。
把常出现的order可以做个cache，不用重复计算了。
【在 s*********s 的大作中提到】
: 写了个brute-force。总觉得不应该是这样。
| r*******e
发帖数: 7583 | 22 二爷啊，从饭店的利益出发，这种情况肯定是返回combo啊，怎么能不让order
【在 p*****2 的大作中提到】
:
: 可以一个饭店一个饭店的算。算一个饭店就算bruteforce的话也是很快的。一个饭店的
: menu实在是有限。
: 把常出现的order可以做个cache，不用重复计算了。
| p*****2
发帖数: 21240 | 23
如果这样的话，customers要complain了。我估计十有八九要退货了。至少我是不能容
忍这个的。
【在 r*******e 的大作中提到】
: 二爷啊，从饭店的利益出发，这种情况肯定是返回combo啊，怎么能不让order
|
|
