这是道01背包题   ，尽管背包不会  ，可是还是看出来了，递推公式写啊写没写出来，后来一同学说是dfs。这我就開始了A了，

   题意是给你n个重量是Wn的石头  让你放到两个包里面。看他们两个差值最小，而且输出这个差值。

dfs代码

#include 
     
      int sum;int h,T;int a[100];void dfs (int x,int y){    if(x==T)    {        if(y>h)  h=y  ;        return ;    }     if(h==sum/2)   return ;    if(y+a[x]<=sum/2)//等于号一定要有。这样调了好久好久，由于他们有可能相等。
     

dfs(x+1,y+a[x]); dfs(x+1,y); } int main() { while(scanf("%d",&T)==1) { sum=0;h=0; for(int i=0;i<T;i++) { scanf("%d",&a[i]); sum+=a[i]; } // printf("%d\n",sum); dfs(0,0); // printf("%d\n",h); printf("%d\n",sum-2*h); } }

dp代码

#include 
     
      #include 
      
       const int maxx = 2000010;int dp[maxx],a[25],n;int abs(int x){	return (x>0)?x:-x;}int maxxx(int a,int b){	return (a>b)?
      
     

a:b; } int main() { while(scanf("%d",&n)==1) { if(n==1) { scanf("%d",&a[0]); printf("%d",a[0]); continue; } int sum = 0,temp,ans; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum += a[i]; dp[i] = 0; } temp = sum/2; dp[0] = 0; for(int i=1;i<=n;i++) for(int j=temp;j>=a[i];j--) dp[j] = maxxx(dp[j-a[i]]+a[i],dp[j]);//求在【0-temp】最大的数就好了 for(int i=temp;i>=0;i--) if(dp[i]!=0) { ans = dp[i]; break; } printf("%d\n",abs(sum-2*ans)); } return 0; }