将2N个整数分成两组,每组有N个数,并且满足,这两组的差的绝对值最小。

时间:2021-06-02 11:30:31

有人提议说模拟 背包算法....背包算法大概可以表示为给你一个包,然后你让这个包尽可能的有价值,对应的就是,这个包的大小就是 sum(c)/2 (这样就可以让他们的绝对值最小),然后问题来了,这个算法只会视价值来分配,不会执着于时候分成两半........但是,他的解决思维还是可以借鉴的:

背包算法说,我在拿第 i 件的时候,分成两个情况,一种是不拿,一种是拿.

设 dp(i,j,k) 为,从前i件中拿j个数,且不能超过c 的最大值:

这样的话 递归方程  dp(i,j,k) = max( dp(i-1,j-1,k - c[i]) +c[i] , dp(i-1,j,c) );

用 node 链表来存储,分出来的结点索引。 - -|| 然后想来想去,这种方法真心复杂,而且复杂度为O(2^n)方,而且,分完以后...还有再通过那些序列来分数组。琢磨这种方法,主要是想,到底怎么样才可以存储到那些节点。有更好的方法,就提出来参考参考。

class node{
public:
    int index;
    node * next;
    node(int i):index(i),next(NULL){}
};

int iSelectj(int i,int j,int c,node * &p){
    //先判断是否超出了范围,或者数目不够了
    if( c < 0 || i < j)
        return 0x80000000;
    //判断是否已经选够数字了
    if( j == 0 )
        return 0;
    //判断是否不合法
    if(i < 1 )
        return 0x80000000;

    //如果选择这个数的话,就生成这个结点
    node * p1 = new node(i-1);
    int max1 = a[i-1]+iSelectj(i-1,j-1,c-a[i-1],p1);

    //不用的话,就继续用上一层传进来的结点
    int max2 = iSelectj(i-1,j,c,p);
    cout << "iSelectj("<<i<<","<<j<<","<<c<<"):";

    if( max1 > max2){
        cout << "use "<< a[i - 1]<< "+iSelectj("<<i-1<<","<<j-1<<","<<c-a[i-1]<<")" << endl;
        //如果 max1 > max2 说明用了这个结点,那么max2后面采用的结点都不要
        deleteNode(p->next);
        p->next = p1;
        return max1;
    }else{
        cout << "use " << "iSelectj("<<i-1<<","<<j<<","<<c<<")" << endl;
        //如果 max2 > max1 ,说明没用这个结点,则采用 max2后面的结点,删除p1带的结点
        deleteNode(p1);
        return max2;
    }
}

再接着,突然想起 C++的标准算法里面有个全排列的,发现用他的话,也可以很容易的写出来,不过,时间复杂度差不多。

C++ STL中提供了std::next_permutation与std::prev_permutation可以获取数字或者是字符的全排列,其中std::next_permutation提供升序、std::prev_permutation提供降序。

int new_mask[] = {1,1,1,0,0,0};
    int a[] = { 3,1,11,2,7,8};
    int n = sizeof(a)/sizeof(a[0]);
    int c = 0;
    for( int i = 0;i<n;i++)
        c+=a[i];
    c = c/2;
    int max =0x80000000;
    int item[] = {-1,-1,-1,-1,-1,-1};
    do 
    {
        int sum = 0;
        for(int j = 0;j<n;j++){
            if(new_mask[j]){
                sum = sum+a[j];
            }
        }
        if(sum < c && sum > max ){
            max = sum;
            memcpy(item,new_mask,sizeof(new_mask));
        }
    } while (prev_permutation(new_mask,new_mask+n));

    cout << "use :";
    for(int j = 0;j<n;j++){
        if(item[j]){
            cout << a[j] <<  " ";
        }
    }
    cout << endl;
    cout << "max :" << max << endl;

 

最后,附上第一种方法的源代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

class node{
public:
    int index;
    node * next;
    node(int i):index(i),next(NULL){}
};

void showNode(node * p){
    p = p->next;
    while (p){
        cout << p->index <<" ";
        p = p->next;
    }
    cout << endl;
}

void deleteNode(node * &p){
    node * h = p;
    while(h){
        node * temp = h;
        h = h->next;
        delete temp;
    }
    p = NULL;
}

const int a[] = { 3,1,11,2,7,8};
const int n = sizeof(a)/sizeof(a[0])/2;
int sum =0;
int c = 0;

int num = 0;

int iSelectj(int i,int j,int c,node * &p){
    //先判断是否超出了范围,或者数目不够了
    if( c < 0 || i < j)
        return 0x80000000;
    //判断是否已经选够数字了
    if( j == 0 )
        return 0;
    //判断是否不合法
    if(i < 1 )
        return 0x80000000;

    //如果选择这个数的话,就生成这个结点
    node * p1 = new node(i-1);
    int max1 = a[i-1]+iSelectj(i-1,j-1,c-a[i-1],p1);

    //不用的话,就继续用上一层传进来的结点
    int max2 = iSelectj(i-1,j,c,p);
    cout << "iSelectj("<<i<<","<<j<<","<<c<<"):";

    if( max1 > max2){
        cout << "use "<< a[i - 1]<< "+iSelectj("<<i-1<<","<<j-1<<","<<c-a[i-1]<<")" << endl;
        //如果 max1 > max2 说明用了这个结点,那么max2后面采用的结点都不要
        deleteNode(p->next);
        p->next = p1;
        return max1;
    }else{
        cout << "use " << "iSelectj("<<i-1<<","<<j<<","<<c<<")" << endl;
        //如果 max2 > max1 ,说明没用这个结点,则采用 max2后面的结点,删除p1带的结点
        deleteNode(p1);
        return max2;
    }
}


int main(void) {
    for( int i = 0;i<2*n;i++)
        sum+=a[i];
    c = sum/2;

    node * h = new node(-1);
    int max = iSelectj(2*n,n,c,h);
    for( auto t: a)
        cout << t << " ";
    cout << endl;
    cout << "max = " <<max << endl;
    cout << "use :";

    showNode(h);
    deleteNode(h);
    
    cout << "execute: " << num << endl;

    system("pause");
        return 0;
}