Jobdu MM分水果
生活随笔
收集整理的這篇文章主要介紹了
Jobdu MM分水果
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目1420：Jobdu MM分水果
題目描述：
Jobdu團(tuán)隊(duì)有倆PPMM，這倆MM干啥都想一樣。一天，富強(qiáng)公司給團(tuán)隊(duì)贊助了一批水果，胡老板就把水果派發(fā)給了這倆MM，由她們自行分配。每個(gè)水果都有一個(gè)重量，你能告訴她們怎么分才使得分得的重量差值最小嗎？
?輸入有多組數(shù)據(jù)，每組數(shù)據(jù)第一行輸入水果個(gè)數(shù)n(1<=n<=100)，接下來一行輸入n個(gè)重量wi(0<=wi<=10^5)。
對每組輸入輸出一行，輸出可以得到的最小差值。
510 20 30 10 10
我們利用動(dòng)態(tài)規(guī)劃來做。假設(shè)所有水果總重為sum, 那么其中一個(gè)人所能分得的水果重量w范圍一定在 0 - sum/2之間，二者差值最小，所以在sum/2時(shí)，查看一個(gè)人分到的水果重量。
相當(dāng)于背包問題中體積一定，可以裝最大的價(jià)值是多少
#include <stdio.h> #include <string.h>#define Max(a, b) (a > b)?(a):(b);int n, sum; int fruit[100]; int dp[5000001];int MinDiff(){int i, j;int first, second, ans;int half = (sum >> 1);memset(dp, 0, sizeof(dp));for (i = 0; i < n; ++i){for (j = half; j >= fruit[i]; --j){dp[j] = Max(dp[j], dp[j-fruit[i]] + fruit[i]);}}return sum - 2 * dp[half]; }int main(int argc, char *argv[]) {int i;while (scanf("%d", &n) != EOF){sum = 0;for (i = 0; i < n; ++i){scanf("%d", &fruit[i]);sum += fruit[i];}printf("%d\n", MinDiff());}return 0; }
總結(jié)
以上是生活随笔為你收集整理的Jobdu MM分水果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 两船载物问题
- 下一篇： 九度-1463-招聘会