高手请进，C++算法极度挑战！！！本人已经一天没合眼了

Question

做什么游戏用的。RealVal的值的范围是什么呢？

Answer 1

pfans(pfans) (  )：谢谢关注：如：
有一个数组int SumVal[8]={2，3，4，5，6，7，8，9}；我有一个数28，我要查找5个数，满足相加的和为x,满足28-x的余数最小且>0(已经知道肯定有这样的5个数），将差值返回。

Answer 2

feifei2001(动力A6)：
我已经在另外的程序中实现了int RealVal值的限定，为简单化问题，可以说
int RealVal的取值满足在数组中肯定有这样的。就是说如上面的值28，肯定有满足28-x的余数最小且>0，主要是怎么查找实现的问题？谢谢关注！！！

Answer 3

由小到大从SumVal中取出数来与RealVal相减。如果大于0且个数小于UnitNum则继续循环。能找到这个数的。是这样理解吗？

Answer 4

这是一个排列组合问题
      如果你在数组一定存在这样的值，就好办了。
    数组是一个有序的数列。所以每次从最大的数开始计算，如果28-x小于0，
    数组的指针就退一，这样就能的出了
   程序如下：
    int GetMin(int UnitSum,int RealVal)
      {  int all=0;
           int min=0;
         while(i<=0){
               for(j=0;j<UnitSum;j++)
                  all+=SumVel[i-j];
               minx =RealVal-all;
             if(minx<0){
                  i--  ;
              else{
              if(minx<min)
                {  min=minx;
                    i--;  } 
               else 
                     return min;
              
                 }
           }
          如果不正确的地方请指出，我是直接在这儿写出的，没有调试

Answer 5

yingxiong(竹剑傲江湖)：谢谢你的关心，每次传递的UnitNum是一个确定的数，如果传4，则表示在int SumVal[8]中肯定有这样的4个数的组合，而且只能是4个。其实实际问题比这复杂得多，但是我把问题简化出来了，比如，我在其他地方已经判断肯定有这样的数了。如果各位有兴趣，我可以把整个问题说出来！！！！

Answer 6

wsjdouble(废墟)：你的代码没有实现将UnitNum个数相加。

Answer 7

你必须实现数组的排列组合，即实现
  UnitSum
C
  8
然后将RealVal的值与每个组合数值之和进行比较

Answer 8

我觉得你的问题最迷惑人的就是求出最小余数且大于0，这样给人的感觉似乎有很复杂的遍历和递归（回朔）。其实换一个角度可以使问题简化许多，比如找28的最小余数可以转换为找数组中是否有一组数的和为27，没有的话再找26...以此类推。
判断数组中的某些数的和是否为某数应该是比较简单的。
至于计算出几个数相加得到的最终结果，你自己想办法吧。 ：）
bool testval(int num, int *items, int len)
{
  if (len == 0)
     return FALSE;
  for (int loop=0; loop<len; loop++)
     if (num == items[loop])
        return TRUE;
  for (int i=0; i<len ;i++)
  {
     if (testval(num-items[i], &items[i], len-i-1))
        return TRUE;
  }
  return FALSE;
}
main()
{
   int SumVal[8] = { ... };
   int val = 28;
   int result;
   for (result=val-1; result>0; result++)
      if (testval(result, SumVal, 8))
          break;
   printf("最接近的数%d", result);
}

Answer 9

第一步：把所有可能的和保存在一个数组里面，
inta[255];
voidcomb2(intn,intr)
{
intj,ri=1;
a[1]=n;
do{
if(ri!=r)//没有搜索到底
{
if(ri+a[ri]>r)//是否回溯
{
a[ri+1]=a[ri]-1;
ri++;
}else{//回溯
ri--;
a[ri]--;
}
}else{
                         int count = 0 ;
for(intj=1;j<=r;j++)
                        {
                                count += SumVal[a[j]];
cout<<a[j]<<"";
                        }
                        cout<< count ;//可以把count保存在一个数组里
cout<<endl;
if(a[r]==1)//是否回溯
{
ri--;
a[ri]--;
}else{//回溯
a[ri]--;
}
}
}while(a[1]>r-1);
}
第二步：就可以和RealVal比较了，得出最小的数，（应该很简单了把）

Answer 10

因为你的数组是由小到大的，所以可以立刻建立哈夫曼树（无须循环）
建立后从根结点出发，遍历取权重最接近RealVal的结点，若其子树的叶子数不为UintSum的，则取权重第二接近的结点……

Answer 11

#include <algorithm>
//p中的前m个数表示 p中n个数的一种C(m,n)选择
//这个函数返回下一个可能的选择。函数要求p[0]到p[m-1]是排序的 p[m]到p[n-1]也是排序的
//建议参考一下stl的函数 next_permutation (它是下一个排序的情况)
bool next_select(int *p,int n,int m)
{
for(int i=m; --i>=0;)
{
for(int j=m; j<n && p[j]<=p[i]; ++j);
if( j==n ) continue;
if( m-i < n-j ) std::swap_ranges(p+i,p+m,p+j);
else std::swap_ranges(p+j,p+n,p+i);
return true;
}
return false;
}int SumVal[8];
int value(int UnitSum,int RealVal,int *index)
{
for(; UnitSum--; RealVal -= SumVal[*index++]);
return RealVal;
}
int GetMin(int UnitSum,int RealVal)
{
int index[8]={0,1,2,3,4,5,6,7};
int v,min_value = INT_MAX;
if( (v=value(UnitSum,RealVal,index))>0 ) min_value = v;
for( ;next_select(index,8,UnitSum); )
{
v = value(UnitSum,RealVal,index);
if( v>0 && v<min_value)
min_value = v;
}
return min_value;
}

Answer 12

sorry!
我上面的代码写错了，main中的循环应该是
for (result=val-1; result>0; result--)
代码经过测试，没有问题。

Answer 13

xfeixiang(小飞象) 的逆向思维的方法很不错啊
楼主 把整个问题说一下吧
学习学习

Answer 14

//在一个数组中找出m个数的和与另一数跟接近
//VC++运行
#include <iostream.h>void init();//初始函数
void getmin(int level);//递归int actnum,minnum;//当前值,被记录最小值
int totalnum;//总的输入数
int min[100],act[100];//记录当前值所含数,被记录最小值所含数
bool visited[100];//是否被访问过
int data[]={2,3,4,5,6,7,8,9};//具体数据
int UnitSum,RealVal;//要求几个数来逼近,逼近的数void init()
{

totalnum=sizeof(data)/sizeof(int);
UnitSum=5;
RealVal=28;
for(int i=0;i<totalnum;i++)
{
visited[i]=false;
}
minnum=0;
actnum=0;
}void getmin(int level)
{
int i,nextlevel;
int temp;
nextlevel=level+1;
if(level==UnitSum)
{
if(RealVal-actnum>0&&actnum>minnum)
{
minnum=actnum;
for(i=0;i<totalnum;i++)
    min[i]=act[i];
}
}
else
{
for(i=0;i<totalnum;i++)
{
if(visited[i]==false)
{
visited[i]=true;
act[level]=i;
temp=data[i];
                actnum+=temp;
getmin(nextlevel);
actnum-=temp;
visited[i]=false;
}
}
}
}void main()
{
init();
getmin(0);
cout<<minnum<<endl;
for(int j=0;j<UnitSum;j++)
{
cout<<data[min[j]]<<" ";
}
}