Python练习册--求两序列的和最小差值序列

# 题目

有两个序列a,b,大小都为n,序列元素的值任意整形数,无序;

要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。

# 下面几种算法都是不对的!


# 思路

  1. 先说我的吧.先将两个列表排序并计算两个列表和之差diff.然后遍历,用取大列表的元素去减小列表的元素之差与diff/2相比较,绝对值最小,就调换该两元素,再重新排序重复之.有点像贪心算法,局部最优,但是全局并不一定是最优解.

  2. 方案二(效果不理想)

    1. 将两序列合并为一个序列,并排序,为序列Source

    2. 拿出最大元素Big,次大的元素Small

    3. 在余下的序列S[:-2]进行平分,得到序列max,min

    4. 将Small加到max序列,将Big加大min序列,重新计算新序列和,和大的为max,小的为min。

  3. 回溯法(backtracking)

    当前数组a和数组b的和之差为

       A = sum(a) - sum(b)
    

    a的第i个元素和b的第j个元素交换后,a和b的和之差为

       A' = sum(a) - a[i] + b[j] - (sum(b)- b[j] + a[i])
              = sum(a) - sum(b) - 2 (a[i] - b[j])
              = A - 2 (a[i] - b[j])
    

    设x= a[i] - b[j]

        |A| - |A'| = |A| - |A-2x|
    

    假设A> 0,当x在(0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小, x越接近A/2效果越好, 如果找不到在(0,A)之间的x,则当前的a和b就是答案。

  4. 另外一种,就是先合并成一个数组再组成.


# 解法

  1. Code:

    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    # @Date    : 2014-12-02 12:57:18
    # @Author  : Linsir (vi5i0n@hotmail.com)
    # @Link    : https://linsir.org
    
    def switch(a,b):
        a.sort()
        b.sort()
        flag = 0
        diff = (sum(a) - sum(b)) / 2.0 
        if diff < 0:
            flag = 1
            a, b = b, a
            diff = abs(diff)
        x = -1
        y = -1
        tmp = None
        for i in range(len(a)):
            for j in range(len(b)):
                if b[j] < a[i]:
                    diff2 = abs(a[i] - b[j] - diff)
                    if tmp is None:
                        tmp = diff2
                        x, y = i, j
                    if tmp > diff2:
                        tmp = diff2
                        x, y = i, j
                        
        a[x], b[y] = b[y], a[x]
        if flag:
            a, b = b, a
        diff = abs(sum(a) - sum(b))
        a.sort()
        b.sort()
        return a, b, diff
    
    if __name__ == '__main__':
        # a = [93, 91, 90, 82, 81, 74, 74, 74, 74, 68,]
        # b = [60, 57, 49, 48, 48, 45, 36, 35, 29, 22]
        # a = [3, 4, 10, 15]
        # b = [3, 7, 10, 20]
        # a=[69,31,54,47]
        # b=[99,0,58,42]
        a = [-3,9,10,65]
        b = [5,6,13,55] 
        # print a, b
        tmp = None
        num =0
        while(1):
            a, b, result = switch(a, b)
            print a, b, result
            if tmp is None:
                tmp = result
            if tmp >= result:
                tmp = result
                print "tmp_is:%s" %tmp
                num += 1
            else:
                a, b, result = switch(a, b)
                print a,sum(a)
                print b,sum(b)
                break
        print "num:%s" %num
    
  2. Code:

    def mean( sorted_list ):
        if not sorted_list:
            return (([],[]))
     
        big = sorted_list[-1]
        small = sorted_list[-2]
        big_list, small_list = mean(sorted_list[:-2])
     
        big_list.append(small)
        small_list.append(big)
     
        big_list_sum = sum(big_list)
        small_list_sum = sum(small_list)
     
        if big_list_sum > small_list_sum:
            return ( (big_list, small_list))
        else:
            return (( small_list, big_list))
     
    tests = [   [1,2,3,4,5,6,700,800],
                [10001,10000,100,90,50,1],
                range(1, 11),
                [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
                ]
    for l in tests:
        l.sort()
        print
        print "Source List:\\t", l
        l1,l2 = mean(l)
        print "Result List:\\t", l1, l2
        print "Distance:\\t", abs(sum(l1)-sum(l2))
        print '-*'*40
    
  3. Code:

    #include <iostream>  
    using namespace std;  
    class RunClass  
    {  
       public:  
             void BalanceArray( int array1[],  int array2[],int n1,int n2);  
       private:  
              int Sum(int array[],int n);  
    };  
      
    void RunClass::BalanceArray(int array1[], int array2[],int n1,int n2)  
    {  
      
         if (n1 != n2)  
              return;  
         int *array=new int[n1];  
         if (Sum(array1,n1) < Sum(array2,n2))  
         {  
      
               array= array1;  
               array1 = array2;  
               array2 = array;  
         }  
                bool ifCycle = true;  
                int length = n1;  
                while (ifCycle)  
                {  
                   ifCycle = false;       
                    for (int i = 0; i < length; i++)  
                    {  
                        for (int j = 0; j < length; j++)  
                        {  
                            int itemValue = array1[i] - array2[j];  
                            int sumValue = Sum(array1,n1) - Sum(array2,n2);  
                            if (itemValue < sumValue && itemValue > 0)  
                            {  
                                ifCycle = true;  
                                int item = array1[i];  
                                array1[i] = array2[j];  
                                array2[j] = item;  
                            }  
                        }  
                    }  
                }  
    }  
      
    int RunClass::Sum(int array[],int n)  
    {  
           int sum = 0;  
      
           for (int i = 0; i < n; i++)  
            {  
              sum += array[i];  
            }  
           return sum;  
     }  
      
    int main()  
    {  
       int array1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 90, 0, 0, 100 };  
       int array2[] = { -1, -2, -100, -3, 99, -222, -2, -3, -5, -88, 11, 12, 13 };  
      
       RunClass  a;  
       a.BalanceArray(array1, array2,13,13);  
      
       for(int i=0;i<13;i++)  
           cout<<array1[i]<<"  ";  
       cout<<endl;  
      
       for(int i=0;i<13;i++)  
           cout<<array2[i]<<"  ";  
       cout<<endl;  
      
       return 0;  
      
     }
    
  4. 还有一种:

    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    def change(llist,rlist):
          r=lenth-1
          tflag=1
          global flag
          global cha
          while r>=0 and tflag:
                for l in range(lenth):
                      if((rlist[r]-llist[l])*2<=cha and rlist[r]>llist[l]):
                            rlist[r],llist[l]=llist[l],rlist[r]
                            rlist.sort()
                            llist.sort()
                            cha=sum(rlist)-sum(llist)
                            print llist 
                            print rlist
                            tflag=0
                            break
                else:
                      r -=1
          if(r<0):
                flag=0
          return (llist,rlist)          
    
          
    if(__name__=='__main__'):
    
          sourcelist=[93, 91, 90, 82, 81, 74, 74, 74, 74, 68, 60, 57, 49, 48, 48, 45, 36, 35, 29, 22]
    
          # a=[69,31,54,47]
          # b=[99,0,58,42]
          # sourcelist = a + b 
          sourcelist.sort()
          lenth=len(sourcelist)/2
          llist=sourcelist[:lenth]
          rlist=sourcelist[lenth:]
          cha=sum(rlist)-sum(llist)
          flag=1
          while flag
                (llist,rlist)=change(llist,rlist)
          llist.sort()
          rlist.sort()
          print llist,sum(llist)
          print rlist,sum(rlist)
          print cha
    

# 总结

测试了几组数据,都不能全部都是最优解

上述几种算法都是不对的!

上面的做法只是每次交换一个就做判断,如果每次交换两个后做判断呢?

如果两个序列分别是[-3,9,10,65]和[5,6,13,55],按算法这就是最优解了。可是显然[-3,5,13,65]和[6,9,10,55]更好。


参考地址:

  1. 华为面试题
  2. yuucyf的专栏
  3. 椰子的专栏
  4. 小田的专栏

--EOF--


>看不到评论?GFW!!!