面试题（从给定的N个正数中选取若干个数之和最接近M） algorithm

这道题跟捞鱼问题一样，都是刚进实验室新生培训那会儿做过的题目，不过这个是一师姐当时找工作的面试题。
如题，并输出该子序列
测试用例：2，9，5，7，4，11，10
分别输出最接近33、40、47、60的子序列
分析：N个数之和接近M，将M看做一个容量的背包，这个题目就变成了典型的01背包，M容量下求最优解并输出最优方案，这在01背包中都整理过，上代码：
关于0、1背包问题：参考http://blog.csdn.net/lsjseu/article/details/8750462
【面试题（从给定的N个正数中选取若干个数之和最接近M）】

#include using namespace std; char state[11][101]; /* 设 N <= 10 M <= 100 记录路径 */ int dp[101]; /* 使用一维数组01背包 */ int value[11]; /* 本题可将费用与价值看做同一值 */ int i, j; void main() { int N, M; scanf("%d", &N); for(i = 0; i < N; ++i) { scanf("%d",&value[i]); } while(scanf("%d", &M) != EOF) { memset(dp,0,sizeof(dp)); /* 01背包 */ for(i = 0; i < N; ++i) { for(j = M; j >= value[i]; --j) { int tmp = dp[j-value[i]] + value[i]; if(tmp > dp[j]) { dp[j] = tmp; state[i][j] = 1; } } } printf("最接近值：%d\n",dp[M]); /* 输出方案 */ i = N; //第几个商品 j = M; //当前背包容量 while(i-- >= 0) { if(state[i][j] == 1) { printf("%d ",value[i]); j -= value[i]; } } printf("\n"); } }

输出结果如下图

文章图片

补充：找出所有可能的组合出来（改自：July博客 http://blog.csdn.net/v_JULY_v/article/details/6419466 ）

#include #include using namespace std; int value[11]; int i, j; list seq; /* 寻找可能的序列 */ void find_seq(int sum, int index) { if(sum <= 0 || index < 0) return; if(sum == value[index]) { seq.reverse(); printf("%d ", value[index]); for(list::iterator iter = seq.begin(); iter != seq.end(); ++iter) { printf("%d ", *iter); } printf("\n"); seq.reverse(); } seq.push_back(value[index]); // 放入 find_seq(sum-value[index],index-1); seq.pop_back(); find_seq(sum,index-1); // 不放入 } void main() { int N, M; scanf("%d", &N); for(i = 0; i < N; ++i) { scanf("%d",&value[i]); } scanf("%d", &M); printf("可能的序列：\n"); find_seq(M,N-1); }