UVA 562 Dividing coins

题目大意：给你若干硬币，让你分成两份，使其绝对值之差尽量的小。

很容易想到，我们需要枚举出这些硬币可能凑出的所有面值，那么，怎么去算出这些硬币可能凑出的面值就是我们需要解决的问题了。

令dp[i]数组来保存是否可以凑出i的面值的结果。可以为1，否则为0.sum为这些硬币的面值之和。

显然dp[0]=1，有一份一分钱都没有事肯定可以的。那么dp[sum]=1，有一份可以囊括所有的硬币。

那么既然dp[0]是可以的，那么dp[0+coin[j]]也一定可以凑出来，同理dp[sum-coin[j]]也是可以的；如此推广下去，dp[coin[j]]可以，dp[coin[j]+coin[k]]也可以………………我们获得的可以凑出来的面值数量会越来越多。这样的算法复杂度为n的平方吧。

最后，我们去寻找距离总面值数一半的(sum/2)差值最小的那个数j，那么我们最后输出的结果显然是sum-j*2。

下面贴代码

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int coin[101];
 5 int dp[101000];
 6 int main()
 7 {
 8     int ncase,sum,i,j,m;
 9     cin>>ncase;
10     while(ncase--)
11     {
12         memset(dp,0,sizeof(dp));
13         sum = 0;
14         cin>>m;
15         for(i = 1;i <= m;i++)
16         {
17             cin>>coin[i];
18             sum += coin[i];
19         }
20         dp[0] = 1;
21         for(i = 1;i <= m;i++)
22             for(j = sum;j >= coin[i];j--)
23                 if(dp[j - coin[i]])
24                     dp[j] = 1;
25         for(i = sum / 2;i >= 0;i--)
26             if(dp[i])
27             {
28                 j = i;
29                 break;
30             }
31         /*for(i = 0;i <= sum;i++)
32             cout<<i<<"->"<<dp[i]<<" ";
33         cout<<endl;*/
34         cout<<sum - 2 * j<<endl;
35     }
36     return 0;
37 }