有一个无序，元素个数为2n的正整数数组，把这个数组分成两个n的子数组，子数组和最接近？

 

将其转化为0/1背包问题，将容量为n的背包放入元素，元素的体积为1，重量为其大小，如何装使其接近于重量sum/2，

sum为2n的和。

 

1 #include 
     
       2 #include 
      
        3  4 using namespace std; 5  6 int main() 7 { 8     int n=5; 9     int nArray[10] = {
   1,5,7,8,9,6,3,11,20,17};10 11     //0/1背包12     int sum=0;13     for(int i=0; i<2*n; i++)14     {15         sum+=nArray[i];16     }17     //容量为n的背包,装满n件物品时，能达到的价值,只考虑小于等于sum/2的价值18     bool dp[n+1][sum/2+1];19     memset(dp,0,sizeof(dp));20     dp[0][0]=true;21     for(int k=2*n-1; k>=0; k--)22     {23         for(int i=1; i<=n; i++)24         {25             for(int v=0; v<=sum/2; v++)26             {27                 if(dp[i-1][v] && v+nArray[k]<=sum/2)28                 {29                     dp[i][v+nArray[k]]=true;30                 }31             }32         }33     }34     int maxV;35     for(int v=sum/2; v>=0; v--)36     {37         if(dp[n][v])38         {39             maxV=v;40             break;41         }42     }43     cout<
       
        <<"/"<
        
         <