分类目录归档:算法

hash表取模技巧

在使用hash表的时候,由于hash表的size不可能无限大,我们必须将hash function求出来的index值映射到hash表的size范围内。一般情况下都是采取取模的形式index % size,但是modulus操作要进行除法运算,在数据量大的时候效率较低,这时候我们可以将size设置为2的某次方,这样只要将index & (size – 1)就可以求得模值,至于为什么是这样,原理很简单,我就不在此赘述了。

【动态规划】二维背包问题之0 1背包(二维 0-1背包)

最近算法设计课要做期末作业,我们组的题目是二维0-1背包问题,为此我再次温习了一下动态规划。

动态规划是个十分有趣而且重要的算法,据说这个算法的发明者当初是在为美国国防部做的一个项目中发明了这个算法,为了让别人不知道他在做什么随便起了一个名字叫做动态规划(dynamic programming),因此你永远不要试图从它的名字中理解它的思想。

继续阅读