首页 > 代码库 > 正整数分组

正整数分组

技术分享
 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstdio>
 6 #define _xx ios_base::sync_with_stdio(0);cin.tie(0);
 7 using namespace std;
 8 typedef long long ll;
 9 int dp[10005], a[105];
10 int main()
11 {_xx
12     int n, sum;
13     while(cin >> n)
14     {
15         sum = 0;
16         memset(dp, 0, sizeof dp);
17         dp[0] = 1;
18         for(int i = 1; i <= n; i++)
19         {
20             cin >> a[i];
21             sum += a[i];
22         }
23         for(int i = 1; i <= n; i++)
24             for(int j = sum; j >= a[i]; j--)
25                 dp[j] = dp[j -a[i]] | dp[j];
26         int ans = 1000000;
27         for(int i = 0; i <= sum; i++)
28             if(dp[i] == 1) ans = min(ans, abs(sum - i - i));
29         cout << ans << endl;
30     }
31     return 0;
32 }
View Code

 

正整数分组