还是数组分割问题

题目概述：有一个没有排序，元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。 


谁能分析一下这道题，为什么考虑用动态规划解决，

同时看这个http://en.wikipedia.org/wiki/Subset_sum_problem 发现是个np问题

8 个解决方案

#1

http://blog.csdn.net/jcwKyl/archive/2009/02/23/3926444.aspx

这里的思路，你可以参考一下

#2

upup

#3

我之前做过一个类似的题目，只是总的数字个数不是一定是偶数。
做法一个类似DP的BFS。。。或者你可以看一下。

#include<iostream>
#include<algorithm>

using namespace std;
const int maxl=450010;//元素总和，如果这个总和过大，导致内存不够的话，那么我这个方法就不能用了:(
bool b[101][maxl]={0};
int a[101];
int n;
struct node
{
	int num,val;
}queue[maxl*100];
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	int i,j,sum=0;
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}

	if(n==1)
	{
		printf("0 %d\n",a[0]);
		return 0;
	}
	queue[0].num=0;queue[0].val=0;
	b[0][0]=1;
	int half=sum/2,numHalf=n/2,size=1,p;
	for(j=0;j<n;j++)
	{
		p=size;
		for(i=0;i<size;i++)
		{
			queue[p].num=queue[i].num+1;
			queue[p].val=queue[i].val+a[j];
			if(!b[queue[p].num][queue[p].val])
			{
				b[queue[p].num][queue[p].val]=1;
				//printf("get the val %d\n",queue[p].val);
				if(queue[p].num<=numHalf)
				{
					//printf("in queue!\n");
					p++;
				}
			}
		}
		size=p;
	}
	int ans=0;
	if(n&1)
	{
		for(i=half;i>0;i--)
		if(b[numHalf+1][i])
		{
			ans=i;
			break;
		}
		if(ans==0)
		{
			for(i=half;i>0;i--)
			if(b[numHalf][i])
			{
				ans=i;
				break;
			}
		}
	}
	else
	{
		for(i=half;i>0;i--)
			if(b[numHalf][i])
			{
				ans=i;
				break;
			}
	}
	ans=ans<(sum-ans)?ans:(sum-ans);
	printf("%d %d\n",ans,sum-ans);
	return 0;
}

#4

引用 1 楼 hairetz 的回复:

http://blog.csdn.net/jcwKyl/archive/2009/02/23/3926444.aspx 

这里的思路，你可以参考一下

你以为我再发帖之前没有搜索过吗，这样没用的链接不但是浪费我的时间，同时也是浪费你的时间

#5

如果都是正整数的话,应该不是np级的。复杂度应该不超过O(N^2*Sum)，其中Sum是2N个数的加和！

可以定义一个大的bool数组来做。

#6

如果真的是动态规划问题
我想应该要牵涉到线性方程了
可以考虑用matlab里的函数

#7

问题：有8个物件，重量分别为4,10,9,5,1,5,3,8。现要从中取4个装入背包，使包内外物件总重之差的绝对值最小。
下面是用matlab写的动态规划程序：
clear;
clc;
myinf=100000000000000000;
w=[4,10,9,5,1,5,3,8];
n=size(w,2);%物件个数
%定义状态列表
statlist(1)=struct('S',0,'D',0,'open',0,'overtip',0);
statlist(end)=[];
%初状态加入
statlist(end+1)=struct('S',zeros(1,n),'D',sum(w),'open',true,'overtip',false);
while 1
    nls=size(statlist,2);%状态列表长度
    disp(nls);
    %找open==true且|S|最小的状态
    mn=myinf;
    mni=-1;
    for i=1:nls
        cadS=sum(statlist(i).S);
        if statlist(i).open==true...
                &&cadS<mn...
                &&cadS<n/2
            mn=cadS;
            mni=i;
        end
    end%得到mn和mni
    if mni==-1%所有状态均已经关闭（达终态）或完成
        break;
    end
    statlist(mni).open=false;%关闭(关闭后永不开启)
    stat=statlist(mni);%值引用
    %推进stat
    for i=1:n%对于每个物件i
        if stat.S(i)==0%如果物件i尚未加入
            %加入物件i,生成邻接状态
            linstat=stat;
            linstat.S(i)=1;
            linstat.open=true;
            if linstat.overtip==false...%如果加入物件i前尚未跨过平衡点
                    &&linstat.D>=2*w(i)%且加入物件i也不会跨过平衡点
                linstat.D=linstat.D-2*w(i);
            elseif linstat.overtip==false...%如果加入物件i前尚未跨过平衡点
                    &&linstat.D<2*w(i)%且加入物件i后跨过平衡点
                linstat.D=2*w(i)-linstat.D;
                linstat.overtip=true;
            else%如果加入物件i前就已经跨过了平衡点
                linstat.D=linstat.D+2*w(i);
            end%linstat已制成
            %看listat是否已存在于statlist
            exist=false;
            for j=1:nls
                if all(statlist(j).S==linstat.S)
                    exist=true;
                    break;
                end
            end%得到exist
            if exist==true%如果已存在 
                if linstat.D<statlist(j).D%如果新的目标值更优
                    statlist(j)=linstat;%覆盖旧状态
                end
            else%如果不存在
                statlist(end+1)=linstat;%新增状态
            end
        end
    end
end
%在状态空间中找最优解
mn=myinf;
mni=-1;
for i=1:size(statlist,2)
    if sum(statlist(i).S)==n/2 ...%是解
        &&statlist(i).D<mn%且目标值更小
        mn=statlist(i).D;
        mni=i;
    end
end
disp('最终结果:');
disp('目标值:');
disp(statlist(mni).D);
disp('包内物件集:')
disp(statlist(mni).S);
运行结果：
目标值:
     1

包内物件集:
     1     1     0     1     0     0     1     0

#8

  帮楼主顶一下