从M个数中取出任意N个数，N<=M 使其和接近值S,并给出是由M中那几个位置的数组合而成
例如M有10个数（1.2.5.2.3.6.7.8.6.0）
目标数S设定15
可以得到15=1+5+7+2四个数组成，是由M中第1个位置，第3个位置，第7个位置，第2个位置组成
小弟新手碰到这么个难题，请大家不领赐教，谢过了

给个思路也好呀，最好有历程。茫茫论坛，没人教给一二吗？

这个不是很难，用列举法就可以实现。

给个程序思路吧，谢过了

算法我是白痴，给出最笨但是理解简单的就行

这个题多用递归完成，是个比较经典的组合问题，给个代码你参考吧：

#include<stdio.h>
int fun(int *a,int *b,int n,int m)
{
    int i,j,s;
    for(i=s=0;b[i]>=0;i++)s+=a[b[i]];
    if(s==m)return 1;
    if(s>m)return 0;
    for(j=n;a[j];j++)
    {
        b[i]=j;
        b[i+1]=-1;
        if(fun(a,b,j+1,m))return 1;
        b[i]=-1;
    }
    return 0;
}
void main()
{
    int a[]={1,2,5,2,3,6,7,8,6,0};    //递归要求原始数组必须以数据0结尾，否则得不到正确结果。
    int i,j=15,b[10];
    b[0]=-1;
    if(fun(a,b,0,j))
    {
        for(i=0;b[i]>=0;i++)printf("%d+",a[b[i]]);
        printf("%c=%d,对应数据位置分别是：",8,j);
        for(i=0;b[i]>=0;i++)printf("第%d个位置,",b[i]+1);
        printf("\n");
    }
    else printf("没有和为%d的组合\n",j);
}

以前弄的一个代码,用了背包问题里面的dp思想~

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#include<string.h>

int Comp(const void* p1,const void* p2);

void Input(size_t** a,size_t** k,size_t* n,size_t* m);

void Fun(size_t a[],size_t k[],size_t n,size_t m);

void Output(const size_t a[],const size_t k[],size_t m);

int main( void )
{
    size_t* a=NULL;
    size_t* k=NULL;
    size_t n=0;
    size_t m=0;

    Input(&a,&k,&n,&m);

    Fun(a,k,n,m);
    
    Output(a,k,m);

    free(a);
    free(k);

    return 0;
}

int Comp(const void* p1,const void* p2)
{
    if (*(size_t*)p1>*(size_t*)p2)
        return 1;
    else if (*(size_t*)p1<*(size_t*)p2)
        return -1;

    return 0;
}

void Input(size_t** a,size_t** k,size_t* n,size_t* m)
{
    size_t i;

    puts("请输入元素个数和所求定值和:");

    if (scanf("%u%u",(unsigned* )n,(unsigned* )m)!=2)
        exit(0);

    ++*m;
    *a=malloc(*n*sizeof(**a));

    if (*a==NULL)
    exit(0);

    memset(*a,0,*n*sizeof(**a));

    *k=malloc(*m*sizeof(**k));

    if (*k==NULL)
    exit(0);

    memset(*k,-1,*m*sizeof(**k));

    printf("请输入%u个元素:\n",*(unsigned* )n);

    for (i=0;i!=*n;++i)
    if (scanf("%u",(unsigned* )&((*a)[i]))!=1)
        exit(0);
}

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    size_t next=0;
    size_t rear=n-1;
    size_t MinWeight=0;
    
    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;
        
    for (;next!=rear&&MinWeight+a[next]<=m;MinWeight+=a[next++]);

    if (!next)
        return ;
        
    for (i=a[0];;++i)
    {

        while (i+a[rear]>m)
            if (rear--<next)
                return ;

        for (j=rear;j>k[i];--j)
            k[i+a[j]]=j;
    }
}

void Output(const size_t a[],const size_t k[],size_t m)
{
    size_t i=0;
    size_t j=0;

    for (;i!=m;++i)
        if (k[i]!=-1)
        {
            printf("%u=%u",(unsigned)i,(unsigned)a[k[i]]);

            for (j=i;j-=a[k[j]];)
                printf("+%u",(unsigned)a[k[j]]);

            puts("");
        }
}

二进制也可以表示数组组合状态,就算枚举所有组合也不一定要用到这种方法递归~

二进制状态组合思路甚好，不过对于超过32位的是不是就要做超大位数二进制计算了？对动态规划算法不甚理解，显然6楼这种完全组合的递归算法效率不高。
7楼代码free(k)时出现0x00431cd0错误提示.

这个bug没怎么发现,或者是因为引用内存出现越界的情况,或者我会去看看具体情况

PS:应该是K的数组开少了,正常来说当a[i]的值正好等于n的时候恰好越界,所以简单来说把malloc那里开大一点就可以了~

[此贴子已经被作者于2018-5-6 18:45编辑过]