给定的输入是:缓存的大小s，内存条目的数量n，以及一系列的内存访问。
给出可能的最小缓存未命中数。
示例:
s = 3, n = 4 1 2 3 1 4 1 2 3 min_miss = 4
我整天都被困住了。提前致谢!
您可以决定缓存采取的任何行为。例如，您不必接受一个条目，即使它已被访问。而且它不需要是常规的。您不需要遵循固定的“规则”来缓存。
最佳答案
尝试关注 http://en.wikipedia.org/wiki/Page_replacement_algorithm#The_theoretically_optimal_page_replacement_algorithm - 当你需要换掉一些东西时，换掉在尽可能长的时间内不会再次使用的元素。由于您提前获得了整个内存访问序列，这对您来说是可行的。这显然是局部最优的，至少在缓存变满后的第一次缓存未命中之前是这样，因为到那时每个其他策略都至少有一次缓存未命中。对我来说这不是全局最优的——搜索我在 http://www.stanford.edu/~bvr/psfiles/paging.pdf 找到了证据并声称其最优性的其他证据确实存在，但时间更长。
关于algorithm - 算法-给定一个内存访问序列，给出缓存未命中的最小次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18426627/