编程之美--数组分割
有一个没有排序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，
并且使两个子数组的和最接近？
解法三：
定义：isOK[i][v]表示是否可以找到i个数，使得它们之和等于v初始化isOK[0][0]=true;isOK[i][v]=false;(i>0,v>0)for (int k=1; k<=2*n;++k){ for (int i=min(k,n);i>=1;--i) { for (int v=1;v<=Sum/2;++v)//Sum是整个数组的和 { if (v>=data[k]&&isOk[i-1][v-data[k]])//data是2n个数的数组 isOk[i][v] = true; } }}vector<int> res[100][1000]; int main() { int data[10] = {1,6,88,15,23,64,9,7,5,21}; int sum = 0; for(int i = 0 ; i < 10 ; ++ i) sum += data[i]; int n = 5; int isOk[100][1000]; memset(isOk,0,sizeof(isOk)); isOk[0][0] = 1; for (int k=0; k<2*n;++k) { for (int i=min(k,n);i>=1;--i) { for (int v=1;v<=sum/2;++v)//Sum是整个数组的和 { if (v>=data[k]&&isOk[i-1][v-data[k]])//data是2n个数的数组 { isOk[i][v] = 1; res[i][v] = res[i-1][v-data[k]]; res[i][v].push_back(data[k]); } } } } for(int i = sum / 2 ; i >= 0 ; -- i) { for(int j = 0 ; j < n ; ++ j) { if(isOk[j][i]) { cout<<"组合:" copy(res[j][i].begin(),res[j][i].end(),ostream_iterator<int>(cout," ")); cout<<endl<<"结果为"<<i<<endl; return 0; } } } return 0; }
[解决办法]
就是背包问题嘛，接分了。。。
[解决办法]
背包问题。推荐LZ百度一下 背包问题九讲
[解决办法]
这个本质上就是背包思想，楼主的问题是：怎么得到是哪几个数的和呢？？？
这个要想知道是哪几个数的和也是很简单的，只要加上一个while循环，在里面判定当前状态是由哪个状态推导出来的就可以了。。
附上我的代码，给楼主参考一下。。
#include <iostream>using namespace std;//有一个没有排序，元素个数为N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。const int N= 2;int arr[] ={0,3,1, 11,2};const int SUM = 17;int splitArray2N_to_N(){ int dp[2*N+1][N+1][SUM/2+2]; /* 用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案，在这里i>=j,c<=S 状态转移方程： //限第i个物品 不取 dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i]，dp(i-1,j,c)} dp(2N,N,SUM/2+1)就是题目的解 */ memset(dp,0,sizeof(dp)); //初始化 for(int i=1;i<=2*N;i++) { for(int j=1;j<=min(i,N);j++) { for ( int k= 1; k<= SUM/2+1; ++k)//先赋值,因为如果数组中某个值大于SUM/2+1,则下一个for循环中dp[i][j][s]全,没赋值,错 { dp[i][j][k] = dp[i-1][j][k]; } for(int s= SUM/2+1; s>=arr[i]; s--) //再取其中较大值 { dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i],dp[i-1][j][s]); } } } //因为这为最终答案 dp[2*N][N][<SUM/2>];其中<SUM/2>为>=SUM/2的最小整数.(如->4,7->4) int iTotalNum=2*N; int j=N; int iEven= SUM % 2+ SUM/2; //如SUM为偶数,则取其一半;如SUM为奇数,则取其一半加1 int s= iEven; cout<<"第一个数组中的元素为:"; while( iTotalNum > 0 ) { if(dp[iTotalNum][j][s]==dp[iTotalNum-1][j-1][s-arr[iTotalNum]]+arr[iTotalNum]) //判定这个状态是由哪个状态推导出来的 { cout<<arr[iTotalNum]<<" "; //取出arr[i] j--; s-=arr[iTotalNum]; } iTotalNum--; } cout<<endl; return dp[2*N][N][iEven];}int main(void){ int iSum1= splitArray2N_to_N(); //将一个长度为N的数组分割成个长度为N的数组,且两数组的和的差的绝对值最小,即和最接近 cout<<"第一个数组的和为:"<< iSum1<<endl; system("pause"); return 0;}
[解决办法]
[code=C/C++][/code]
#include <iostream>
using namespace std;
//有一个没有排序，元素个数为N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。
const int N= 2;
int arr[] ={0,3,1, 11,2};
const int SUM = 17;
int splitArray2N_to_N()
{
int dp[2*N+1][N+1][SUM/2+2];
/*
用dp(i,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案，在这里i>=j,c<=S
状态转移方程：
//限第i个物品 不取
dp(i,j,c)=max{dp(i-1,j-1,c-a[i])+a[i]，dp(i-1,j,c)}
dp(2N,N,SUM/2+1)就是题目的解
*/
memset(dp,0,sizeof(dp)); //初始化
for(int i=1;i<=2*N;i++)
{
for(int j=1;j<=min(i,N);j++)
{
for ( int k= 1; k<= SUM/2+1; ++k)//先赋值,因为如果数组中某个值大于SUM/2+1,则下一个for循环中dp[i][j][s]全,没赋值,错
{
dp[i][j][k] = dp[i-1][j][k];
}
for(int s= SUM/2+1; s>=arr[i]; s--) //再取其中较大值
{
dp[i][j][s] = max(dp[i-1][j-1][s-arr[i]]+arr[i],dp[i-1][j][s]);
}
}
}
//因为这为最终答案 dp[2*N][N][<SUM/2>];其中<SUM/2>为>=SUM/2的最小整数.(如->4,7->4)
int iTotalNum=2*N;
int j=N;
int iEven= SUM % 2+ SUM/2; //如SUM为偶数,则取其一半;如SUM为奇数,则取其一半加1
int s= iEven;
cout<<"第一个数组中的元素为:";
while( iTotalNum > 0 )
{
if(dp[iTotalNum][j][s]==dp[iTotalNum-1][j-1][s-arr[iTotalNum]]+arr[iTotalNum]) //判定这个状态是由哪个状态推导出来的
{
cout<<arr[iTotalNum]<<" "; //取出arr[i]
j--;
s-=arr[iTotalNum];
}
iTotalNum--;
}
cout<<endl;
return dp[2*N][N][iEven];
}
int main(void)
{
int iSum1= splitArray2N_to_N(); //将一个长度为N的数组分割成个长度为N的数组,且两数组的和的差的绝对值最小,即和最接近
cout<<"第一个数组的和为:"<< iSum1<<endl;
system("pause");
return 0;
}
[解决办法]
感谢LZ分享,接分了