九度笔记之 1420：Jobdu MM分水果

题目1420：Jobdu MM分水果

题目描述：
Jobdu团队有俩PPMM，这俩MM干啥都想一样。一天，富强公司给团队赞助了一批水果，胡老板就把水果派发给了这俩MM，由她们自行分配。每个水果都有一个重量，你能告诉她们怎么分才使得分得的重量差值最小吗？

输入：
输入有多组数据，每组数据第一行输入水果个数n(1<=n<=100)，接下来一行输入n个重量wi(0<=wi<=10^5)。

输出：
对每组输入输出一行，输出可以得到的最小差值。

样例输入：
510 20 30 10 10

算法分析
这道题和题目1358：程博的平均主义可以看作同一道题。

我们利用动态规划来做。假设所有水果总重为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[j] = dp[j]||dp[j-num[i]];

在更新dp的时候一定注意是要从sum/2 到 num[i], 这样才能保证每个水果出现了0次或1次。

如果dp从num[i]到sum/2更新，那么 dp[j-num[i]] 就可能是已经放入第i个水果的结果。类似的如

题目1455：珍惜现在，感恩生活（每个元素数量有有限多个的，可以转为多个单独的）

题目1434：今年暑假不AC

题目1499：项目安排

对于每个元素数量无限的，dp从num[i] 到最多递增更新

题目1455：珍惜现在，感恩生活

源程序

//============================================================================
// Name        : judo1358.cpp
// Author      : wdy
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//similar to   judo1358
#include <iostream>
int num[101];
using namespace std;
 
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;
        }
    }
}
 
void judo(){
    int n;
    while(std::cin>>n){
        allocate(n);
    }
}
int main() {
    judo();
    return 0;
}
/**************************************************************
    Problem: 1420
    User: KES
    Language: C++
    Result: Accepted
    Time:770 ms
    Memory:3888 kb
****************************************************************/

补充：软件开发 , C++ ,