51 Nod 1007 正整數分組【類01背包】

1007 正整數分組

基準時間限制：1 秒空間限制：131072 KB 分值: 10

難度：2級算法題

將一堆正整數分為2組，要求2組的和相差最小。

例如：1 2 3 4 5，將1 2 4分為1組，3 5分為1組，兩組和相差1，是所有方案中相差最少的。

Input

第1行：一個數N，N為正整數的數量。
第2?-?N+1行，N個正整數。
(N?<=?100,?所有正整數的和?<=?10000)

Output

輸出這個最小差

Input示例

Output示例

題目鏈接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1007

分析：

本題要求兩個正整數數組的和差，那么要使得兩個和差最小，那么必定每個數組是越靠近sum/2的（就是和的中間點）

那么我們就可以把這道題目轉化為簡單的01背包了。

下面給出AC代碼：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 10010
 4 int a[N]; 
 5 int n;
 6 int dp[N];
 7 int  main(void)
 8 {    
 9      while(scanf("%d",&n)!=EOF)
10      {
11        int sum=0;
12        for(int i=1;i<=n;i++)
13        {
14              cin>>a[i];
15              sum+=a[i];//挑選出一些數字，是的越靠近sum/2,那么就是背包問題了 
16        }
17        memset(dp,0,sizeof(dp));
18        for(int i=1;i<=n;i++)
19                for(int j=sum/2;j>=a[i];j--)
20                    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
21        cout<<abs((sum-dp[sum/2])-dp[sum/2])<<endl;
22      }
23       return 0;
24 }

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257424.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257424.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257424.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！