任意5个数中和最接近400的

来源：百度知道 编辑：UC知道 时间：2024/09/24 18:28:40
任意输入5个数
求其中哪几个数加起来最接近且不超过400
注意 是其中哪几个数相加哦,不是哪两个数也不是哪三个数.
比如:输入200 30 100 80 60
就应该是 200+30+100+60=390最接近且不超过400

// 递归遍历 找出大小于400的组合
// 困了，写的很乱
// foo.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#define LARGE 99999
int test[6] = {200,2,100,80,199,0};
int o1[6] , o2[6];
int min = LARGE;

int foo(int * b , int * e , int s)
{
if(b == e)
{
int m;
if(s < 0)
{
m = LARGE;
o1[1] = 0;
}
else
{
m = s;
o1[1] = 1;
}
if(m < min)
{
min = m;
memcpy(o2 , o1 , sizeof(o1));
}
return m;
}

o1[e-b]=1;
int d1 = foo(b+1 , e , s-*b);
o1[e-b]=0;
int d2 = foo(b+1 , e , s);

return (d1 < d2)?d1:d2;

}

int _tmain(int argc, _TCHAR* argv[])
{
int d = foo(test , test+5 , 400);

for(int i=0;i<5;i++)
{
if(o2[5-i])
printf("%d &