将2N个整数分成两组，每组有N个数，并且满足，这两组的差的绝对值最小。
将2N个整数分成两组，每组有N个数，并且满足，这两组的差的绝对值最小。
forxtz
发布于 2020-10-10 16:40:32
发布于 2020-10-10 16:40:32
有人提议说模拟 背包算法....背包算法大概可以表示为给你一个包，然后你让这个包尽可能的有价值，对应的就是，这个包的大小就是 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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-09-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读