九度笔记之 1420：Jobdu MM分水果 - KingEasternSun的专栏 - 博客频道 - CSDN.NET
Jobdu团队有俩PPMM，这俩MM干啥都想一样。一天，富强公司给团队赞助了一批水果，胡老板就把水果派发给了这俩MM，由她们自行分配。每个水果都有一个重量，你能告诉她们怎么分才使得分得的重量差值最小吗？
Read full article from 九度笔记之 1420：Jobdu MM分水果 - KingEasternSun的专栏 - 博客频道 - CSDN.NET
Jobdu团队有俩PPMM，这俩MM干啥都想一样。一天，富强公司给团队赞助了一批水果，胡老板就把水果派发给了这俩MM，由她们自行分配。每个水果都有一个重量，你能告诉她们怎么分才使得分得的重量差值最小吗？
我们利用动态规划来做。假设所有水果总重为sum, 那么其中一个人所能分得的水果重量w范围一定在 0 - sum/2之间，
也许有人会问 sum为奇数时，w范围应该在0 - （sum/2+1）之间，当一个人分得sum/2+1时，另外一个人分得的必定是sum/2,这和我们求质数时，测试范围从 2到sqrt(n)一样。
我们的问题就转化为 一个人所分得的重量w从 sum/2 到0 哪个重量可以实现。
我们当给一个人什么水果都不分的话，就可以实现0. 即 dp[0] = true;
当我们选择第i个水果时，该水果重量为num[i], 我们判断在第i个水果分配给这个人之前 dp[w]是否为true,或者dp[w-num[j]]是否为true;
如果从前i-1个水果中挑出某几个可以组成重量w，那么dp[w] = true;
如果从前i-1个水果中挑出某几个可以组成重量w-num[i], 那么加上第i个水果的重量就可以组成w，所以
- dp[j] = dp[j]||dp[j-num[i]];
在更新dp的时候一定注意是要从sum/2 到 num[i], 这样才能保证每个水果出现了0次或1次。
- void allocate(int n){
- int sum=0;
- for(int i = 0;i<n;i++){
- std::cin>>num[i];
- sum+=num[i];
- }
- int maxPercent = sum>>1;
- bool *dp = new bool[maxPercent+1];
- for(int i = 1;i<maxPercent+1;i++)
- dp[i] = false;
- dp[0] = true;
- for(int i = 0;i<n; i++){
- for(int j = maxPercent; j>=num[i]; j--)
- dp[j] = dp[j]||dp[j-num[i]];
- }
- for(int i = maxPercent;i>0;i--){
- if(dp[i]){
- std::cout<< sum-2*i<<std::endl;
- break;
- }
- }
- }
03 | int n, k, a[101], v[101], t,i,m; |
04 | void dfs(int x, int y) { |
05 | int i; |
06 | if (y > t) |
07 | return; |
08 | if (y > k) { |
09 | k = y; |
10 | } |
11 | if (k == t) |
12 | return; |
13 | for (i = x; i <= n; i++) |
14 | if (!v[i]) { |
15 | v[i] = 1; |
16 | dfs(i + 1, y + a[i]); |
17 | v[i] = 0; |
18 | } |
19 | } |
20 | int main() { |
21 | while(scanf("%d",&n)==1) { |
22 | t=0; |
23 | for(i=1;i<=n;i++) { |
24 | scanf("%d",a+i);t+=a[i]; |
25 | } |
26 | k=-1;m=t;t/=2;memset(v,0,sizeof(v)); |
27 | dfs(1,0); |
28 | printf("%d\n",m-k*2); |
29 | }} |
