本文共 824 字，大约阅读时间需要 2 分钟。

/*回溯法-子集和数问题 */ #include 
   
    int M,n;int w[100];int x[100];void SumOfSub(int s, int k, int r)//w数组必须是递增的{     //s=w[1]*x[1]+...+w[k-1]*x[k-1]     //r=w[k]+...w[n]      //w[i]需要按非降次序排列     int i;    x[k]=1;    for(i=1; i<=k; i++)       printf("%d", x[i]);    printf("/n");    if(s+w[k]==M) //子集找到    {        printf("ans:");        for(i=1; i<=k; i++)            printf("%d", x[i]);        printf("/n");    }else if(s+w[k]+w[k+1]<=M)        SumOfSub(s+w[k], k+1, r-w[k]);        if(s+r-w[k]>=M && s+w[k+1]<=M)//当在什么情况下可以不选择w[k]而也能找到子集？    {        x[k]=0;        SumOfSub(s, k+1, r-w[k]);    }} int main(){    int s,k,r;    n=4;    w[1]=7;    w[2]=11;    w[3]=13;    w[4]=24;    M=31;        s=0;    k=1;    r=55;        SumOfSub(s, k, r);    getchar();    return 0;}
   

可以看成背包问题，但是只能求出一个解。数组元素当成是物品，物品的价值与重量是元素的值，背包的容量是T;

转载地址：http://tpeti.baihongyu.com/