[Jobdu] 题目1420：Jobdu MM分水果

- 日理万妓 2021-09-30 00:22 149阅读 0赞

**题目描述：**

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

**输入：**

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

**输出：**

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

**样例输入：**

5
    10 20 30 10 10

**样例输出：**

0
    
    用dp求解，代码如下：

#include <iostream>
    #include <cstdio>
    #include <vector>
    using namespace std;
    
    int n,s;
    vector<int> v;
    vector<bool> d;
    
    int main(int argc,char* argv[]){
        //freopen("input.txt","r",stdin);
        while(cin>>n){
            v.resize(n);
            s = 0;
            for(int i=0;i<n;i++){
                cin>>v[i];
                s += v[i];
            }
            int min = s;
            int tmp,p=s/2+1;
            d.resize(p);
            for(int i=0;i<p;i++){
                d[i] = false;
            }
            d[0] = true;
            for(int i=0;i<n;i++){
                for(int j=p;j>=v[i];j--){
                    if(d[j-v[i]] == true){
                        d[j] = true;
                        tmp = s-2*j;
                        if(tmp<0){ 
                            tmp = 0-tmp;
                        }
                        min = tmp<min?tmp:min;
                        if(min==0){
                            break;
                        }
                    }
                }
            }
            cout<<min<<endl;
        }
        return 0;
    }

典型的动态规划题目，类似于背包问题，有一点注意只要判断sum/2即可，min=0时可直接退出，尽量避免做无用功。

转载于:https://www.cnblogs.com/easonliu/archive/2012/08/16/2642530.html