51Nod 1007：正整数分组（01背包）-白红宇

51Nod 1007：正整数分组（01背包）

阅读量：5041 次

发布时间：2019-06-12

本文共 1166 字，大约阅读时间需要 3 分钟。

基准时间限制：1 秒空间限制：131072 KB 分值: 10

关注

将一堆正整数分为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示例

思路

一开始看到这题感觉是贪心，但是又觉得好麻烦，完全没思路，不知道怎么贪，百度找了一下，发现竟然是背！包！！

仔细想一下也很好理解，可以看做是n个数字放在两个袋子里，所以对于每个数字，肯定会放在这两个袋子中的其中一个，即对于一个袋子来说，数字非0即1（1代表放进去，0代表不放）。因为题目要求的是求两个袋子里的最小差值，所以把袋子的容量设为这些数字总和的1/2 。去计算在这个袋子里最多能装下的价值是多少（把每个数字看做价值和体积均为本身数值的物品），因为最后要求的是差值，所以要用总价值减去装进一个袋子中的价值*2

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define ll long long#define ms(a) memset(a,0,sizeof(a))#define pi acos(-1.0)#define INF 0x3f3f3f3fconst double E=exp(1);const int maxn=1e6+10;using namespace std;int a[maxn];int dp[maxn];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); int n; cin>>n; int res=0; for(int i=0;i
                
                 >a[i]; res+=a[i]; } for(int i=0;i
                 
                  =a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]); int _=abs(res-2*dp[res/2]); cout<<_<

转载于:https://www.cnblogs.com/Friends-A/p/10324407.html

你可能感兴趣的文章