Description

给你N个整数，能不能从中找出几个数，使这几个数的和等于M

Input

第一行 给你t ,t表示有几组测试数据。
每组数据包括二行：第一行给你整数N(2＜N＜1000)，M(1＜=M＜=10000).第二行有N个数，且这N个数都小于M，两个数中间有一个空格隔开。

Output

每个测试只输出一行，不能有多余的空格。
如果可以得到和M，则输出“yes”；否则输出“no”。

Sample Input

2
6 10
1 2 3 4 5 6
6 40
2 4 6 8 10 1

Sample Output

yes
no

[此贴子已经被作者于2007-11-15 19:43:08编辑过]

#include<stdio.h>
#include<stdlib.h>
int compar(const void *a,const void *b)
{
int *aa=(int *)a,*bb=(int *)b;
return *bb-*aa;
}
int main()
{
int n,m,i,j,sum,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int base[n],flag=0;
for(i=0;i<n;i++)
scanf("%d",&base[i]);
qsort(base,n,sizeof(int),compar);
for(i=0;i<n;i++)
{
sum=m;
for(j=i;j<n;j++)
{
if(sum>=base[j]) sum=sum-base[j];
if(sum==0) { flag=1; break;}
}
}
if(flag==1) printf("yes\n");
else printf("no\n");
}
return 0;
}

我的AC了的 爽

怎么办啊

你再想几组特殊数字看看 或者你有什么好的方法介绍一下

再看看这个
#include<stdio.h>
#include<stdlib.h>
int comp_ints(const void *p1,const void *p2)
{
int i1=*(int *)p1;int i2=*(int *)p2;
return i1-i2;
}
int main(void)
{
int i,j,j1,j2,n,m,t,isture,sum,l,count=0;
int a[1002];
scanf("%d",&t);
for(i=0;i<1002;i++)
a[i]=0;
for(i=0;i<t;i++)
{
isture=0;count=0;
sum=0;
scanf("%d%d",&n,&m);
for(j=0;j<n;j++)
scanf("%d",&a[j]);
qsort (a,n,sizeof(int),comp_ints);
n=n-1;
l=n;
for(j2=n;j2>=0;j2--)
{
l=j2;
while(l!=-1)
{
sum=0;
if(l!=j2)
sum+=a[n];
for(j1=l;j1>=0;j1--)
{
sum=sum+a[j1];
if(sum>=m)
{
if(sum==m)
{
isture=1;
break;
}
else
{
sum=sum-a[j1];
}
}
}

if(isture==1)
break;
l--;
}
if(isture==1)
break;
}
if(isture==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}

JOJ是哪个学校的 把差不多的题的网址贴出来下 我看哈

我的同学作的
背包法解决求和问题
#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;
}

#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;
}