郵票分你一半

時間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：3 描述

小珂最近收集了些郵票，他想把其中的一些給他的好朋友小明。每張郵票上都有分值，他們想把這些郵票分成兩份，并且使這兩份郵票的分值和相差最小（就是小珂得到的郵票分值和與小明的差值最小），現(xiàn)在每張郵票的分值已經(jīng)知道了，他們已經(jīng)分好了，你知道最后他們得到的郵票分值和相差多少嗎？ 輸入

第一行只有一個整數(shù)m（m<=1000),表示測試數(shù)據(jù)組數(shù)。
接下來有一個整數(shù)n(n<=1000)，表示郵票的張數(shù)。
然后有n個整數(shù)Vi(Vi<=100)，表示第i張郵票的分值。

輸出

輸出差值，每組輸出占一行。

樣例輸入

2 5 2 6 5 8 9 3 2 1 5

樣例輸出

0 2

AC碼：

#include<stdio.h> #include<string.h> int num[1005],dp[50005]; int main() {int T,n,i,t,j,sum;scanf("%d",&T);while(T--){scanf("%d",&n);sum=0;memset(dp,0,sizeof(dp));for(i=0;i<n;i++){scanf("%d",&num[i]);sum=sum+num[i];}t=sum/2;for(i=0;i<n;i++){for(j=t;j>=num[i];j--){if(dp[j]<dp[j-num[i]]+num[i])dp[j]=dp[j-num[i]]+num[i];}}printf("%d\n",sum-2*dp[t]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 456 邮票分你一半的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。