我们可以采用与0-1背包问题相反的顺序遍历，从而可以得到 O(CN) 的解法，伪代码如下：
for i=0..N-1 for c=w[i]..C f[c]=max{f[c],f[c-w[i]]+v[i]}; 复制代码这个伪代码与0-1背包伪代码只是 C 的循环次序不同而已。0-1背包之所以要按照 v=V..0的逆序来循环。这是因为要保证第i次循环中的状态 f[i][c] 是由状态 f[i-1][c-w[i]] 递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果 f[i-1][c-w[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果 f[i][c-w[i]]，所以就可以并且必须采用 c=w[i]..C 的顺序循环。这就是这个简单的程序为何成立的道理。实现代码如下：
/** * 完全背包问题-仿01背包解法 */ int knapCompleteLike01(int N, int C, int w[], int v[]) { int *f = (int *)calloc(sizeof(int), C+1); int i, c; for (i = 0; i < N; i++) { for (c = w[i]; c <= C; c++) { f[c] = max(f[c], f[c-w[i]] + v[i]); } printf("%d: ", i+1); printIntArray(f, C+1); } <span>return</span> f[C];}
复制代码
数学是科学之基础，数字题往往也是被面试玩出花来。数学本身是有趣味的一门学科，前段时间有点不务正业，对数学产生了浓厚的兴趣，于是看了几本数学史论的书，也买了《几何原本》和《陶哲轩的实分析》，看了部分章节，受益良多，有兴趣的朋友可以看看。特别是几何原本，欧几里得上千年前的著作，里面的思考和证明方式真的富有启发性，老少咸宜。本文先总结下面试题中的数字题，我尽量增加了一些数学方面的证明，如有错误，也请指正。本文代码都在 这里。
1.找质数问题题： 写一个程序，找出前N个质数。比如N为100，则找出前100个质数。
分析： 质数(或者叫素数)指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数，如 2，3，5...。最基本的想法就是对 1 到 N 的每个数进行判断，如果是质数则输出。一种改进的方法是不需要对 1 到 N 所有的数都进行判断，因为除了 2 外的偶数肯定不是质数，而奇数可能是质数，可能不是。然后我们可以跳过2与3的倍数，即对于 6n，6n+1, 6n+2, 6n+3, 6n+4, 6n+5，我们只需要判断 6n+1 与 6n+5 是否是质数即可。
判断某个数m是否是质数，最基本的方法就是对 2 到 m-1 之间的数整除 m，如果有一个数能够整除 m，则 m 就不是质数。判断 m 是否是质数还可以进一步改进，不需要对 2 到 m-1 之间的数全部整除 m，只需要对 2 到 根号m 之间的数整除m就可以。如用 2，3，4，5...根号m 整除 m。其实这还是有浪费，因为如果2不能整除，则2的倍数也不能整除，同理3不能整除则3的倍数也不能整除，因此可以只用2到根号m之间小于根号m的质数去除即可。
解： 预先可得2，3，5为质数，然后跳过2与3的倍数，从7开始，然后判断11，然后判断13，再是17...规律就是从5加2，然后加4，然后加2，然后再加4。如此反复即可，如下图所示，只需要判断 7，11，13，17，19，23，25，29... 这些数字。
判断是否是质数采用改进后的方案，即对2到根号m之间的数整除m来进行判断。需要注意一点，不能直接用根号m判断，因为对于某些数字，比如 121 开根号可能是 10.999999，所以最好使用乘法判断，如代码中所示。
/** * 找出前N个质数, N > 3 */ int primeGeneration(int n) { int *prime = (int *)malloc(sizeof(int) * n); int gap = 2; int count = 3; int maybePrime = 5; int i, isPrime; /* 注意：2, 3, 5 是质数 */ prime[0] = 2; prime[1] = 3; prime[2] = 5; <span>while</span> (count < n) { maybePrime += gap; gap = 6 - gap; isPrime = 1; <span>for</span> (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++) <span>if</span> (maybePrime % prime[i] == 0) isPrime = 0; <span>if</span> (isPrime) prime[count++] = maybePrime; } <span>printf</span>(<span>"\nFirst %d Prime Numbers are :\n"</span>, count); <span>for</span> (i = 0; i < count; i++) { <span>if</span> (i % 10 == 0) <span>printf</span>(<span>"\n"</span>); <span>printf</span>(<span>"%5d"</span>, prime[i]); } <span>printf</span>(<span>"\n"</span>); <span>return</span> 0;}
复制代码
题： 给定一个整数N，那么N的阶乘N！末尾有多少个0呢？（该题取自《编程之美》）