首页 > 笔试面试题 > 面试题:从给定的N个正数中选取若干个数之和最接近M

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

2012年6月11日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这道题跟捞鱼问题一样,都是刚进实验室新生培训那会儿做过的题目,不过这个是一师姐当时找工作的面试题。

如题,并输出该子序列

测试用例:2,9,5,7,4,11,10

分别输出最接近33、40、47、60的子序列

分析:N个数之和接近M,将M看做一个容量的背包,这个题目就变成了典型的01背包,M容量下求最优解并输出最优方案,这在01背包中都整理过,上代码:

#include <iostream>
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 <iostream>
#include <list>
using namespace std;

int value[11];
int i, j;
list<int> 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<int>::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);
}

测试:

  • http://blog.csdn.net/w397090770 397090770

    @Yx.Ac
    嘿嘿,貌似也明白了一些。。。

  • Yx.Ac

    哦哦,谢谢!明白了,例如您的例子14,15,20,先运用容量为M=33的方法求得S=29;M与S差值为4,那么问题的解一定是在区间[S,M]与区间[M+1,M+(M-S)-1]中,应用到您的例子即[29,33]与[34,36]中,所以此时再运用容量为M=36时候求一次背包即可!好方法,< 大拇指>@397090770

  • http://blog.csdn.net/w397090770 397090770

    @Yx.Ac
    在贴子http://blog.csdn.net/cwqbuptcwqbupt/article/details/7522997有人提到你类似的问题,也是01背包解法,我没怎么看懂。他推理出来的背包大小为M+1到M+(M-S)-1 范围内。没看懂。。。

  • Yx.Ac

    恩,谢谢提醒,确实没想过和大于M的情况,这种情况怎么用01背包做?请教。@397090770

  • http://blog.csdn.net/w397090770 397090770

    从给定的N个正数中选取若干个数之和最接近M,你用01背包解决是不是有问题?
    如果我输入的数组为14,15,20,M = 33,显然15,20这两个之和为35和M相差2,而你是程序输出的是14,15这两个书,和M相差4,说明这不是最优解,你的程序有问题。
    这种题目是可以用01背包来解,但是并不是简单的for(j = M; j >= value[i]; --j)就行,你这意思就是说最优解之和要小于等于M。