題目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
****************************************************************/
