URAL 1005 Stone Pile

本文主要是介绍URAL 1005 Stone Pile，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   这种题型： Balanced Partition

   刚开始用的方法：

   从最大的开始放，每次放到数量较小的那一堆上，最后看相差为多少。

   这样很容易想，可惜是错的，反例如下。

   5
 10 9 8 7 2

  如果这么算，分的是 (10，7) 和 (9，8，2)  相差2    而最小的答案是（10，8）和（9，7，2）  相差0  

  看了这道题的讨论，基本就两种解法，暴力或DP；

  我是用的DP；

  用bool   dp [ i ] [ j ] 表示只用 i 之前的石头，能否使部分和为 j 。石头重量为 a[ i ] 

 递推式：dp [ i ] [ j ] =dp [ i - 1 ] [ j ]  ||  dp [ i - 1 ] [ j - a[ i ] ]    

 i 的范围：0~n-1      j 的范围： 0~S  (S为总和）      

最后搜索一遍可以达到的分组的和，各自求分成的两堆的差，然后求最小值就行了。

代码如下：

int a[20];int N;
bool dp[20][2000000];
int A(int a){return a>0?a:-a;
}
int main(void)
{ cin>>N;memset(dp,0,sizeof(dp));int S=0;For(i,N) scanf("%d",&a[i]),S+=a[i];dp[0][0]=1;dp[0][a[0]]=1;for(int i=1;i<N;i++){for(int j=0;j<S;j++){dp[i][j]=dp[i-1][j];if(j-a[i]>=0) dp[i][j]=dp[i][j]||dp[i-1][j-a[i]];}}int ANS=inf;for(int i=0;i<S;i++){if(dp[N-1][i]){//若存在一个组合的Sum为i //则这么分组的差为:  S-2i; if(A(S-2*i)<ANS) ANS=A(S-2*i);}}cout<<ANS<<endl;
return 0;
}

这篇关于URAL 1005 Stone Pile的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---