하나의 배열 을 가장 가 까 운 연결 집합 으로 나누다.

1. 문제 설명:
하나의 배열, 예 를 들 어 1, 2, 3, 4, 5.이 배열 을 두 부분 으로 나 누 어 가장 가 깝 게 한다. 예 를 들 어 3, 4 와 1, 2, 5, 하나 와 8 개 는 7 이다.
이 문 제 는 처음 봤 을 때 생각 이 없 었 고, 마지막 으로 인터넷 에서 0 - 1 가방 으로 해결 하 는 것 을 보 니 묘 하 다.
해결 방향:
배열 과 SUM 을 구하 고 배열 을 가장 가 까 운 두 개의 집합 으로 나 누 려 면 각 집합 은 SUM / 2 와 매우 가깝다. 그 중 하 나 는 SUM / 2 보다 클 수 있 고 다른 하 나 는 SUM / 2 보다 작 을 수 있다. 우 리 는 SUM / 2 보다 작 으 면 나머지 요 소 는 자동 으로 다른 부분 이 된다.우 리 는 SUM / 2 를 가방 의 용량 으로 보고 배열 의 모든 요 소 를 물품 으로 본다.이 문 제 는 0 - 1 가방 문제 로 바 뀌 었 다.
2. 문제 설명:
두 개의 배열 A 와 B 가 있 는데 두 배열 의 요 소 를 교환 하여 화 차 를 최소 화해 야 합 니 다.
해결 방향:
두 배열 을 하나의 배열 로 합 쳐 위의 방법 으로 해결 하 자 는 의견 도 있다.사실 이런 방법 은 옳지 않다. 우선 두 배열 의 요소 가 같 을 수 있다. 이렇게 가방 문 제 를 통 해 풀 어 낸 결과 가 반드시 가장 좋 은 것 은 아니다. 다시 한 번 이 방법 을 통 해 얻 은 해 는 각 배열 의 길이 가 원래 배열 의 길 이 를 유지 하 는 것 을 보장 할 수 없다.그래서 이 방법 은 조건 을 만족 시 키 지 못 한다.
실제 방법:http://www.huomo.cn/developer/article-192f8.html
해결 방향:
                  ① 두 개의 배열 을 A 와 B 로 설정 하고 배열 의 길 이 는 N1, N2 이다.배열 A 의 요소 와 SumA 가 배열 B 보다 크다 고 가정 합 니 다.
                      원소 와 SumB, 즉 SumA > = Sum.(이 가설 은 일반적인 것 을 가지 고 있 습 니 다. SumA 가 SumB 보다 작 으 면,
                      이 두 배열 을 교환 할 수 있어 서 항상 비교적 큰 배열 이 앞 에 있 음 을 보증 합 니 다)
                  ② 만약 에 SumA = = SumB 라면 교환 이 필요 없고 최소 차 이 는 0 이다.
                  ③ 만약 SumA > SumB, 령 과 의 차이 Diff = SumA - SumB, 이때 우리 의 작업 은 두 배열 의 것 을 교환 하 는 것 입 니 다.
                      원소, Diff 의 값 을 끊임없이 감소 합 니 다.
                  ④ 배열 A 와 배열 B 에서 각각 하나의 요소 A [i] 와 B [j] 를 선택 하여 교환 하 는데 이들 은 교환 한 후에
                       Diff ' = SumA' - SumB'
                               = (SumA - A[i] + B[j]) - (SumB + A[i] - B[j])
                               = (SumA - SumB) - 2 * (A[i] - B[j])
                               = Diff - 2 * (A[i] - B[j])
                       Diff 가 교환 한 후에 얻 은 Diff 를 줄 이려 면 분명히 2 * (A [i] - B [j]) < = Diff 와 A [i] - B [j] > 0 이 있 습 니 다.
                       그리고 이 두 가지 조건 을 만족 시 키 는 상황 에서 A [i] - B [j] 의 값 이 클 수록 Diff 의 값 이 빨리 수렴 되 고 알고리즘 의 효과 가 좋 습 니 다!
                  ⑤ ④ 의 교환 을 반복 하여 조건 에 맞 는 숫자 를 찾 지 못 할 때 까지 한다.
그 중에서 ④ 번 째 단계 에서 적당 한 A [i] 와 B [j] 를 선택 할 때 A 의 모든 요 소 를 B 의 모든 요소 와 일치 시 키 려 면 이중 순환 이 필요 하 다.
시간 복잡 도 는 O (N1 * N2) 이다.⑤ 단계 의 외층 순환 횟수 는 확실 하지 않 지만 직관 적 으로 이 순환 의 시간 복잡 도 는?
O (MAX (N1, N2) 이기 때문에 전체적인 시간 복잡 도 O (N1 * N2 * Max (N1, N2).N = N1 = N2, 즉 두 배열 이 길 면,
그러면 시간 복잡 도 는 O (N ^ 3):
다음은 상기 두 문제 의 실제 코드 를 드 립 니 다.

#include
#include
#include

#define MAX(a,b)  ((a) >=(b)? a:b) 
int Temp[100][100] = {0};
/***************************problem1 split one array**********************************************/

void SplitArray(int array[], int len)
{
        int i,j;
        int SUM = 0;
        for(i = 0; i < len; i++)
                SUM += array[i];
        SUM = SUM/2;
   
        for(i = 1; i < len; i++)      //the things
        {      
            
                for(j = 1; j <= SUM; j++) //use array[i] in weight j
                {
                        if(((j-array[i]) >= 0) )
                        {
                                
                                  Temp[i][j]= MAX(Temp[i-1][j-array[i]] + array[i], Temp[i-1][j]);  //0-1packet
                        }
                        else
                                  Temp[i][j] = Temp[i-1][j];
                 }
                 
              
          }
}

/*****************************problem2 swap two arrays*************************************/


int array1[10] = {0};
int array2[10] = {0};

void Init(int array[], int len)    //produce arrays
{
   //     srand((int)time(NULL));
        int i;
        for(i = 0; i < len; i++)
        {
                array[i] = rand()%50;
        }
}

void Print(int array[], int len)   //print arrays
{
        int i;
        for(i = 0; i < len; i++)
        {
                printf("%d  ", array[i]);
        }
}

int CalculateSum(int array[], int len)  //calculate sum of arrays
{
        int i;
        int sum = 0;
        for(i = 0; i < len; i++)
        {
                sum = sum + array[i];
        }
        
        return sum;
}

void swap(int *a, int *b)   //swap two elements
{
        int temp;
        temp = *a;
        *a = *b;
        *b = temp;
}              
                

void process(int arrayA[], int arrayB[], int len1, int len2)//main process procedure
{
        int SumA, SumB;
        SumA =  CalculateSum(arrayA, len1);
        SumB = CalculateSum(arrayB, len2);
        printf("sumA is:%d
", SumA);
        printf("sumB is:%d
", SumB);
        int *Amax;
        int *Amin;
        
        int Maxdiff;
        if(SumA > SumB)
        {
                Maxdiff = SumA - SumB;
                Amax = arrayA;
                Amin = arrayB;
        }
                
        else
        {
                Maxdiff = SumB - SumA;
                 Amax = arrayB;
                  Amin = arrayA;
                
        }
        if(SumA == SumB)
        {
                printf("it is already min");
                printf("
");
                return ;
        }
        
        int i, j, temp;
        int index1, index2;
        int stopflag =0;
        for(;;)
        {
                  temp = 0;
                  for(i = 0; i < len1; i++)
                        for(j = 0; j < len2; j++)
                        {
                                if((Amax[i] -Amin [j] > 0) && (Maxdiff >2*(Amax[i]-Amin[j])))
                                {
                                        if(temp < 2*(Amax[i] - Amin[j]))
                                        {
                                                index1 = i;
                                                index2 = j;
                                                temp = 2*(Amax[i] - Amin[j]);
                                                stopflag = 1;
                                                
                                        }
                                 }
                                 
                         }
                         
                if(stopflag)
                {         
                         Maxdiff = Maxdiff - temp;
                         swap(&Amax[index1], &Amin[index2]);
                         stopflag = 0;
                }
                else
                {
                        return ;
                }
         }
}
                         
                        
/******************************************************************************/
int main()
{
      
        int array[7] = {0,1,2,3,4,5,6};
        SplitArray(array, 7);
        
        int i;
        int j;
        int SUM = 0; 
        for(i = 0; i < 7; i++)
                SUM += array[i];
        SUM = SUM/2;
        for(i = 0; i< 7; i++)
        {       for(j = 0; j <= SUM; j++)
              
                printf("%d   ", Temp[i][j]);
                printf("
");
        }
       
        int len1 = 10;
        int len2 = 10;
        int SumA, SumB;
        srand((int)time(NULL));
        Init(array1, len1);
        Init(array2, len2);
        printf("
");
        Print(array1, len1);
        printf("
");
        Print(array2, len2);
        printf("
");
        process(array1, array2, len1, len2);
        Print(array1, len1);
        printf("
");
        Print(array2, len2);
        printf("
");
        SumA =  CalculateSum(array1, len1);
        SumB = CalculateSum(array2, len2);
        printf("sumA is:%d
", SumA);
        printf("sumB is:%d
", SumB);
       
        
}