NYOJ 456 邮票分你一半

http://acm.nyist.net/JudgeOnline/problem.php?pid=456

0/1背包问题

View Code

 1 #include <iostream>
 2 #define maxn 100005
 3 using namespace std;
 4 int ans[maxn], v[maxn];
 5 int main()
 6 {
 7     long t, n, i, j, sum, m;
 8     cin >> t;
 9     while(t--)
10     {
11         cin >> n;
12         sum  = 0;
13         for(i = 0; i < n; i++)
14         {
15             cin >> v[i];
16             sum += v[i];
17         }
18         m = sum/2;
19         for(i = 0; i <= m; i++)
20         ans[i] = 0;
21         for(i = 0; i < n; i++)
22         {
23             for(j = m; j >= v[i]; j--)
24             if(ans[j-v[i]]+v[i] > ans[j])
25             ans[j] = ans[j-v[i]]+v[i];
26         } 
27         cout << sum - 2*ans[m] << endl;
28     }
29     return 0;
30 }