这个求和有点意思

和这个题目有点象...
http://acm.jlu.edu.cn/joj/showproblem.php?pid=2440

----------------解决方案--------------------------------------------------------

我的同学作的
背包法解决求和问题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define YES 1
#define NO 0
#define NOT_FOUND -1

void reverse(int [],int);

int knapsack(int size[],int n,int SIZE,int result[])
{
int **exist;
int **member;
int count;
int i,j;

exist=(int **)malloc(sizeof(int *)*(n+1));
exist[0]=(int *)malloc(sizeof(int)*(n+1)*(SIZE+1));
member=(int **)malloc(sizeof(int *)*(n+1));
member[0]=(int *)malloc(sizeof(int)*(n+1)*(SIZE+1));
for(i=1;i<=n;i++)
{
exist[i]=exist[i-1]+(SIZE+1);
member[i]=member[i-1]+(SIZE+1);
}

exist[0][0]=YES;
for(j=1;j<=SIZE;j++)
exist[0][j]=NO;

for(i=1;i<=n;i++)
for(j=0;j<=SIZE;j++)
{
exist[i][j]=member[i][j]=NO;
if(exist[i-1][j])
{
exist[i][j]=YES;
member[i][j]=NO;
}
else if(j>=size[i-1])
if(exist[i-1][j-size[i-1]])
{
exist[i][j]=YES;
member[i][j]=YES;
}
}
if(exist[n][SIZE])
{
for(count=0,i=n,j=SIZE;i!=0&&j!=0;)
if(member[i][j]==YES)
{
result[count++]=--i;
j-=size[i];
}
else
{
i--;
}
reverse(result,count);
}
else
count=NOT_FOUND;
return count;
}

#define SWAP(a,b) {temp=a;a=b;b=temp;}

void reverse(int x[],int n)
{
int i,j,temp;

for(i=0,j=n-1;i<j;i++,j--)
SWAP(x[i],x[j]);
}

int main(void)
{
int i,j,n,m,num1[1000],num2[1000];
int a,b,p;
int knapsack(int size[],int n,int SIZE,int result[]);
scanf("%d",&n);
while(n--)
{
scanf("%d %d",&a,&b);
for(i=0;i<a;i++)
{
scanf("%d",&num1[i]);
}
p=knapsack(num1,a,b,num2);
if(p>=0)
printf("yes\n");
else
printf("no\n");
}
return 0;
}

----------------解决方案--------------------------------------------------------

根本不用这么麻烦,
基础的DP,类似于背包,且比背包简单
char countline[MAX_M+1]={0};
countline[MAX_M]=1; scanf("%d",&n);
for(i=0;i<n;i++)
{ scanf("%d",&temp); for(i=MAX_M;i>0 && temp<=i;i--) if(countline[i-temp]) countline[i]=1;
} if(countline[M]) printf("Yes"); else printf("No");

我直接在论坛中打的，不知道有没有错误，不过思路就是这样，几行代码就可以做到
时间效率＝空间效率＝O(N^2)

----------------解决方案--------------------------------------------------------

卧龙兄很强

----------------解决方案--------------------------------------------------------
#include <stdio.h>
#include<string.h>
int main()
{
    int v[250000],a,m,n,i,t,k;
    scanf("%d",&k);
    while(k--)
    {
      scanf("%d%d",&n,&m);
      memset(v,0,sizeof(v));
      while(n--)
      {
           scanf("%d",&a);
         for(i=m;i>=1;i--)
         {
            if(v[i]!=0)
            {
                t=a+i;
                if(t<=m) v[t]+=v[i];
            }
         }
         v[a]++;
      }
      if(v[m]==0)
         printf("no\n");
      else
        printf ("yes\n");
   }
    return 0;
}
----------------解决方案--------------------------------------------------------