扩展的母函数（可以做减法的母函数）（当然只要你愿意也可以做乘除！）

nows nowe 分别代表正数范围上的 nowe代表负数范围上的。

nexts nexte 同理。

也就是用新的nowe nexte 存储负数的结果即可。扩展到负数域。这样就可以做减法的母函数的题目啦。

注意这个时候物品可以是负数的。负数的话就存在nowe nexte上即可。

#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
    int n;
    int nows[1000];
    int nowe[1000];

    int nexts[1000];
    int nexte[1000];
    int val[10];
    int i,j,k;
    int sum;
    while(scanf("%d",&n)!=EOF)
    {
        memset(nows,0,sizeof(nows));
        memset(nowe,0,sizeof(nowe));
        memset(nexts,0,sizeof(nexts));
        memset(nexte,0,sizeof(nexte));
        sum = 0;
        for(i=0;i<n;i++){scanf("%d",&val[i]);sum+=val[i];}
        //init .
        nows[0] = 1;
        nows[val[0]] =1;
        nowe[val[0]] =1; 
        
        for(i=1;i<n;i++)
        {
            for(j=-sum;j<=sum;j++)  //对于每一个值
            {
                for(k=-1;k<=1;k++)
                {
                    if(j<0)
                    {
                        if(j+k*val[i]>=0){ nexts[j+k*val[i]] += nowe[-j];}
                        else{nexte[-(j+k*val[i])] += nowe[-j]; }
                    }
                    else
                    {
                        if(j+k*val[i]>=0){nexts[j+k*val[i]] += nows[j];}
                        else{nexte[-(j+k*val[i])] += nows[j]; }
                    }

                }
            }
            memcpy(nows,nexts,sizeof(nexts));
            memcpy(nowe,nexte,sizeof(nexte));
            memset(nexts,0,sizeof(nexts));
            memset(nexte,0,sizeof(nexte));
        }

        for(i=0;i<=sum;i++)
        {
            printf("%d:%d ",i,nows[i]);
        }
        
    }
    
}

View Code

想到了减法。那么乘法很简单。除法则是要扩展到分数。。我觉得应该可以用map来实现吧。其实负数也可以直接用map来实现的。这个解法只是个人无聊之作啦。

扩展的母函数（可以做减法的母函数）（当然只要你愿意也可以做乘除！）

推荐阅读