摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

DP(半個背包問題@@)
總和為奇數的話一定沒辦法配到YES
若為偶數的話，則我們就必須嘗試是否能配到1半的總和
這題提供數據很小的寫法，待網友幫解...

/************************************************************/

#include<stdio.h>  
#include<stdlib.h>
main()
{
 int m,n,a,b,c;
 while(scanf("%d %d",&m,&n)==2)
  {
   for(a=0;a<m;a++)
    {
     int sum=0,flag=0;
     int temp[101]={0},value[10001]={0};
     for(b=0;b<n;b++)
      {
      scanf("%d",&temp[b]);
      sum=sum+temp[b];
      }
     if(sum%2==1)
      {printf("No\n");continue;}
     sum=sum/2;
     for(b=0;b<n;b++)
      {
       for(c=sum-temp[b];c>=0;c--)
        if(value[c+temp[b]]<=value[c]+temp[b])
         {
          value[c+temp[b]]=value[c]+temp[b];
          if(value[c+temp[b]]==sum)
           flag=1;
         }
      }
      if(flag==1)
       printf("Yes\n");
      else
       printf("No\n");
    }
  }
 return 0;
}