z******r
发帖数: 517 | 1 朋友面google被问的，不太清楚有啥比较好的解法。
给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
900ml，但你又不想注入到溢出。
用什么方法注入？ |
s********l
发帖数: 998 | 2 另外2个button 什么情况？
120ml。
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
S*********g
发帖数: 5298 | 3 If the flow speed is constant, you can try some combinations of the three
buttons depending on the behavior of the three buttons.
Mathematically, this becomes
assuming L1 <= B1 <= H1, L2 <= B2 <=H2, L3 <= B3 <=H3
find integers x, y, z such that
L <= x*B1 + y*B2 + z*B3 <= H
120ml。
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
a***g
发帖数: 234 | 4 brute force所有组合,在检查误差
三层循环就够了
不过这个解法不是最优的
120ml。
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
y**i
发帖数: 1112 | 5 那应该就可以用DP？
【在 a***g 的大作中提到】
: brute force所有组合,在检查误差
: 三层循环就够了
: 不过这个解法不是最优的
:
: 120ml。
|
d*******d
发帖数: 2050 | 6 我也有这个感觉.
【在 y**i 的大作中提到】
: 那应该就可以用DP？
|
g*****u
发帖数: 298 | 7 设3个壶每按一次分别由upper和lower bound
u1, l1
u2, l2
u3, l3
两个容量的bound B1和B2
设每个壶要按x_i次，
则这就是一个integer programming问题，更确切的来说就是一个un-bounded knapsack |
b**f
发帖数: 20 | 8 DP should work
I guess we can use the same approach used in coin exchange problem |
z**********g
发帖数: 209 | 9 没看懂，懂得人给讲讲行吗？
120ml。
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
r********t
发帖数: 395 | 10
对啊，这就完了。整数规划有算法的。。。
【在 S*********g 的大作中提到】
: If the flow speed is constant, you can try some combinations of the three
: buttons depending on the behavior of the three buttons.
: Mathematically, this becomes
: assuming L1 <= B1 <= H1, L2 <= B2 <=H2, L3 <= B3 <=H3
: find integers x, y, z such that
: L <= x*B1 + y*B2 + z*B3 <= H
:
: 120ml。
|
r****c
发帖数: 2585 | 11 en
问题不清楚啊
第一，这个误差事先知道吗
第二，误差是每次一样还是random
120ml。
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
s*****g
发帖数: 5159 | 12 ONLINE, best effort solution
assume r spaces are left in the cup, f space has to be filled to reach the r
equirement
assume
large is L +/- l
medium is M +/-m
small is S +/-s
pick the smallest cup X such that X - x is larger than f and X + x is smalle
r than r, if there exists no such option,
find pick the largest cup X such that X + x is less than r
However, if the problem has to be done OFFLINE and a solution has to guarant
teed, then the problem is NP hard from a reduction of knapsack problem,
【在 z******r 的大作中提到】
: 朋友面google被问的，不太清楚有啥比较好的解法。
: 给你一个coffee machine，有large/medium/small三个button，每个button会注入一定
: 量的coffee，且有一定误差。例如，small button会注入100ml+-20ml，即80ml~120ml。
: 现在你有一个cup，有一定容量，例如1L。你想注入超过一个最低限度的coffee，例如
: 900ml，但你又不想注入到溢出。
: 用什么方法注入？
|
s*****g
发帖数: 5159 | 13 Integer programming is NP hard.
【在 r********t 的大作中提到】
:
: 对啊，这就完了。整数规划有算法的。。。
|
m*****g
发帖数: 226 | 14 此题到底是否有解？
如果误差可以变化，是否brute force也没用了 |
