[Coursera] Design and Analysis of Algorithm, Part 2 [Week 5]

Problem set因为看错题差了一分- -

Programming Assignment用了超dirty的办法才搞定，我自己的程序只支持到n=23... 不要叫我程序员，配不上= =
愈发感觉到，programming is nothing but problems at scale. It's all about computation efficiency and memory management...

搞了一天终于做对了。

主要问题出在算组合数的函数，本来是直接用公式算的，这样当n大于21的时候，即使用unsigned long long也会溢出
所以在可能产生溢出情况的时候就改用递归算组合数

圆梦梦剧场 发表于 2013-10-11 01:10
搞了一天终于做对了。

主要问题出在算组合数的函数，本来是直接用公式算的，这样当n大于21的时候，即使用 ...

楼主是怎么处理内存问题的？我的算法算到23时大概要占1G内存囧。。是在一边算一边清除没用的东西的。。

Shuang7 发表于 2013-10-11 06:04
楼主是怎么处理内存问题的？我的算法算到23时大概要占1G内存囧。。是在一边算一边清除没用的东西的。。

这个其实我就沿用了之前几次DP作业的方法。就是每次iteration的时候实际有用的只是上一次的计算结果。
下面这张图，A[S, j]有m个subproblem的话，计算时候用到的所有A[S-{j}, k]都有m-1个subproblem，也就是上一次iteration的结果

所有整个程序只需要：A[0][S][j]和A[1][S][j]

数组第一维取0还是1由最外层的迭代次数，即subproblem size决定。比如m是subproblem size，那么这次的结果保存在A[m%2][S][j]中，计算时候用到上一次结果，就用(m+1)%2作为index。
数组A的第二维S的取值最大为Combination(24,12), 所以只要申请这个大小的空间就好了，然后每个组合数都可以对应到一个index里面。

但是我编写出来的程序要跑20分钟左右吧，没计时过，但差不多要挺久的

圆梦梦剧场 发表于 2013-10-11 10:16
这个其实我就沿用了之前几次DP作业的方法。就是每次iteration的时候实际有用的只是上一次的计算结果。
下 ...

对呀，就是那个Combination(24,12)就把内存搞爆了。。。
我的倒是可以一分钟内出结果。。可能是空间换时间的体现吧= =

圆梦梦剧场 发表于 2013-10-11 10:16
这个其实我就沿用了之前几次DP作业的方法。就是每次iteration的时候实际有用的只是上一次的计算结果。
下 ...

又稍微修改了下，可以跑到n=24... 1min，1G内存。。。我知道有一些内存在那空着，但是没有想到很好的方法去掉= =

圆梦梦剧场 发表于 2013-10-11 10:16
这个其实我就沿用了之前几次DP作业的方法。就是每次iteration的时候实际有用的只是上一次的计算结果。
下 ...

我明白你的方法了，不过那样怎么对应S-{j}到A[1][S][j]中的S呢。。用一个映射表？

Shuang7 发表于 2013-10-11 16:58
我明白你的方法了，不过那样怎么对应S-{j}到A[1][S][j]中的S呢。。用一个映射表？

嗯，你的程序速度好快啊！！！为什么我的这么慢。。。
其实我没有检查到底使用了多少内存诶，我也不知道我到底用了多少。
S对应到index的话，是通过Combinatorial number system

版主，你的程序相比于lecture里面的伪代码，做了什么优化才会到1分钟就跑完的?

圆梦梦剧场 发表于 2013-10-11 23:07
嗯，你的程序速度好快啊！！！为什么我的这么慢。。。
其实我没有检查到底使用了多少内存诶，我也不知道 ...

我感觉自己也没有做什么优化，循环还是那么多层。。不知道区别是不是1:我只算到了n=24，你算了25？（这样理论上会差两倍）; 2: 我没用combinatorial number system你用了。。

plus: 你是用的什么语言呢？我是c++...

再plus: 貌似我的这个实现不是需要Gosper's Hack，而是需要他的逆操作。。因为我是针对1..2^n循环的。。