[编程之美]N个鸡蛋放到M个篮子的方法
admin发表于 2011-07-05 15:11:13
今天看到一个面试题目，题目大意：将n个鸡蛋放到m个篮子，同时保证不能有空篮子，且对于任意小于等于n的数，都能保证有几个篮子的鸡蛋数等于这个数
题目分析
第一眼看到这个题目时，感觉像是整数拆分问题，但是有两个限制：1. 不能有空篮子 2.保证能够针对任意<=n的数，都可以用几个篮子的鸡蛋的和来表示，所以应该不是整数拆分问题。
首先想到是就是穷举，也就是深度搜索，但是如何判断搜索的一个结果是否满足第二个条件呢？
这里可以通过归纳的方法，假设当前的前n个数为Sn，同时任意<=Sn的数都可以用前n个数某些数的和来表示，那么第n+1个数的范围是什么呢？
这里应该可以想到，如果第n+1个数>(Sn) + 1 的话，相当于有间隔，那么(Sn) + 1这个就无法表示，所以第n+1个数应该是<= Sn + 1，这样就可以满足
任意的<=S(n+1) 的数都可以用前n+1个数来表示；
同时在搜索的过程中保证序列是非降序的，而且会有剪枝的方法，实现具体看代码
代码实现
/* * Author: liyangguang* http://www.yaronspace.cn/blog * * File: 1312.cc * Create Date: 2011-07-05 22:39:34 * */ #include#define MAX_N 100000 #define MAX_M 1000 static int s_arrAns[MAX_M]; static int s_iM; static int s_iN; void search(int iCurSum, int iIdx, int iCurNum) { if (iCurSum == s_iN && iIdx == s_iM) { for (int i = 0; i < s_iM; ++i) { printf("%d ", s_arrAns[i]); } printf("\n"); } else if (iCurSum > s_iN || iIdx >= s_iM) { return; } //存在两个剪枝的优化，分别放最少和最多的鸡蛋 if ((iCurSum + iCurNum * (s_iM - iIdx)) > s_iN || iCurSum + (iCurSum +1)*((1 << (s_iM - iIdx)) - 1) < s_iN) { return ; } else { for (int i = iCurNum; i <= iCurSum + 1; ++i) { s_arrAns[iIdx] = i; search(iCurSum+i, iIdx+1, i); } } } int main(int argc, char* argv[]) { while (scanf("%d %d", &s_iN, &s_iM) != EOF) { search(0, 0, 1); } return 0; } /* vim: set ts=4 sw=4: */