一、问题:
1. 有一个无序、元素个数为2n的正整数数组,要求:如何能把这个数组分割为两个子数组,子数组的元素个数不限,并使两个子数组之和最接近。
2. 有一个无序、元素个数为2n的正整数数组,要求:如何能把这个数组分割为元素个数为n的两个数组,并使两个子数组之和最接近。
解法1:(小田)
分为几个阶段:
外阶段:在前k1个数中进行选择,k1=1,2...2*n。
内阶段:从这k1个数中任意选出k2个数,k2=1,2...k1。
内阶段:从这k1个数中任意选出k2个数,k2=1,2...k1。
状态:这k2个数的和为s,s=1,2...sum/2。
决策:决定这k2个数的和有两种决策,一个是这k2个数中包含第k1个数,另一个是不包含第k1个数。
这种做法与0-1背包的方法2相似。很厉害的方法,不需要判断一个节点是否已经使用过。
dp[k][s]表示从前k个数中取任意个数,且这些数之和为s的取法是否存在。
- int main()
- {
- int n, i, k1, k2, s, u;
- cin >> n;
- for (i=1; i<=2*n; i++)
- cin >> A[i];
- int sum = 0;
- for (i=1; i<=2*n; i++)
- sum += A[i];
- memset(dp,0,sizeof(dp));
- dp[0][0]=true;
- // 外阶段k1表示第k1个数,内阶段k2表示选取数的个数
- // 这跟前面陪审团和0-1背包的方法不太一样,他们是在外阶段(外循环)迭代选取个数,内阶段迭代具体选取那个数
- // 这样做需验证选取的数是否出现过,但是可以通过保存Path[个数][状态和]来存储各个状态;
- for (k1=1; k1<=2*n; k1++) // 外阶段k1
- {
- for (k2=k1; k2>=1; k2--) // 内阶段k2
- for (s=1; s<=sum/2; s++) // 状态s
- {
- //dp[k1][s] = dp[k1-1][s];
- // 有两个决策包含或不包含元素k1
- if (s>=A[k1] && dp[k2-1][s-A[k1]])
- dp[k2][s] = true;
- }
- }
- /*根据0-1背包问题改写的方法:事实证明这种方法在不判断选用节点k2是否使用过的情况下,不可取,因为可能会重复调用某一个节点,除非再利用Path[k1][s]保存相应状态的节点。再判断它是否出过。那样的话,就需要用dp[k1][s]保存状态和s,也就是说跟第二个坐标一样。
- for (k1=0; k1<2*n; k1++) // 迭代选取数量
- {
- for (s=0; s<=sum/2; s++) // 状态和sum:s
- if(dp[k1][s]==true)
- for (k2=1; k2<=2*n; k2++) // 选取第k2个
- {
- if (s>=A[k1] ) // if(s>=A[k1] && dp[k2-1][s-A[k1]])
- dp[k1+1][s+A[k2]] = true;
- }
- }
- */
- // 之前的dp[k][s]表示从前k个数中取任意k个数,经过下面的步骤后
- // 即表示从前k个数中取任意个数
- for (k1=2; k1<=2*n; k1++)
- for (s=1; s<=sum/2; s++)
- if (dp[k1-1][s])
- dp[k1][s]=true;
- // 确定最接近的给定值sum/2的和
- for (s=sum/2; s>=1 && !dp[2*n][s]; s--)
- ;
- printf("the differece between two sub array is %d\n", sum-2*s);
- }
解法2.
根据0-1背包问题方法2改写的算法:也好使~这种方式更简便!
只需要改动一点:利用dp[i][m]保存状态和,跟m的值一样。
依然无需测试一个节点是否已经存在,但依然无法保存路径,即无法输出最优解的过程
- struct{
- int wei;
- }node[nMax];
- int main()
- {
- int m, n, i ,w ,dp[mMax],sumN=0;
- while(cin>>n)
- {
- if(n==0) break;
- for (i=1; i<=2*n;i++)
- {
- cin>>node[i].wei;
- sumN += node[i].wei;
- }
- m=sumN/2;
- memset(dp, 0, (m+1)*sizeof(int));
- for (i=1; i<=2*n; i++)
- for ( w=m; w>=node[i].wei; w-- )//根据解法1的分析,必须将权重保存成下标才能满足最优化问题。
- if ( dp[w] < dp[w - node[i].wei] + node[i].wei )
- dp[w] = dp[w - node[i].wei] + node[i].wei;
- cout<<dp[m]<<endl;
- cout<<"the differece between two sub array is: "<<sumN - 2*dp[m]<<endl;
- }
- }
解法3,
- int A[MAXN];
- int dp[MAXN][MAXSUM];
- int Path[MAXN][MAXSUM];
- // dp[k][s]表示取k个数,且和为s的情况下,保存的依然是和s;因为要优化判断
- int main()
- {
- int n, i, k1, k2, s, u,t1,t2;
- cin >> n;
- for (i=1; i<=2*n; i++)
- cin >> A[i];
- int sum = 0;
- for (i=1; i<=2*n; i++)
- sum += A[i];
- memset(dp,-1,sizeof(dp));
- dp[0][0]=0;//初始状态
- for (k1=0; k1<2*n; k1++) // 选取的数量k1
- {
- for (s=0; s<=sum/2; s++) // 状态和s
- if(dp[k1][s]>=0)
- {
- for (k2=1; k2<=2*n; k2++) // 具体选取哪一个k2
- if(dp[k1][s]+A[k2]>dp[k1+1][s+A[k2]] && s+A[k2]<=sum/2)
- {
- t1=k1;t2=s;
- while(t1>0&&Path[t1][t2]!=k2)//验证k2是否在前面出现过
- {
- t2-=A[Path[t1][t2]] ;//减前一个元素的值
- t1--;
- }
- if (t1==0)
- {
- dp[k1+1][s+A[k2]] = dp[k1][s]+A[k2];
- Path[k1+1][s+A[k2]] = k2; //k2保存在Path中
- }
- }
- }
- }
- int maxS=0,maxN=0;
- for (k1=1; k1<=2*n; k1++)
- for (s=1; s<=sum/2; s++)
- if (dp[k1][s]>maxS)
- {
- maxS=dp[k1][s];
- maxN=k1;
- }
- cout<<"the count of num: "<<maxN<<" the max sum of the num: "<<maxS<<endl;
- cout<<"the differece between two sub array is: "<< sum-2*maxS<<endl;
- set<int> index;
- index.clear();
- for (int i=0; i<maxN; i++)
- {
- int id = Path[maxN-i][maxS];
- index.insert(id);
- maxS -= A[id];
- }
- cout<<endl;
- cout<<"the index of selected num: ";
- for(set<int>::iterator iter=index.begin(); iter!=index.end(); iter++) cout<<*iter<<" ";
- }
问题2.
解法1:
但本题还增加了一个限制条件,即选出的物体数必须为n,这个条件限制了内阶段k2的取值范围,(同:公正陪审团问题)并且dp[k][s]的含义也发生变化。这里的dp[k][s]表示从前k个数中取任意不超过n的k个数,且这些数之和为s的取法是否存在
- #define MAXN 101
- #define MAXSUM 100000
- int A[MAXN];
- bool dp[MAXN][MAXSUM];
- // 题目可转换为从2n个数中选出n个数,其和尽量接近于给定值sum/2
- int main()
- {
- int n, i, k1, k2, s, u;
- cin >> n;
- for (i=1; i<=2*n; i++)
- cin >> A[i];
- int sum = 0;
- for (i=1; i<=2*n; i++)
- sum += A[i];
- memset(dp,0,sizeof(dp));
- dp[0][0]=true;
- // 对于dp[k][s]要进行u次决策,由于阶段k的选择受到决策的限制,
- // 这里决策选择不允许重复,但阶段可以重复,比较特别
- for (k1=1; k1<=2*n; k1++) // 外阶段k1
- for (k2=min(k1,n); k2>=1; k2--) // 内阶段k2
- for (s=1; s<=sum/2; s++) // 状态s
- // 有两个决策包含或不包含元素k1
- if (s>=A[k1] && dp[k2-1][s-A[k1]])
- dp[k2][s] = true;
- // 确定最接近的给定值sum/2的和
- for (s=sum/2; s>=1 && !dp[n][s]; s--);
- printf("the differece between two sub array is %d\n", sum-2*s);
- }
问题1的解法3肯定适用,只要最后选择最大值时确定dp[k][s]的k即可;
问题公正陪审团问题1的解法2是否使用,还有待验证。
注意:如果数组中有负数的话,上面的背包策略就不能使用了(因为第三重循环中的s是作为数组的下标的,不能出现负数的),需要将数组中的所有数组都加上最小的那个负数的绝对值,将数组中的元素全部都增加一定的范围,全部转化为正数,然后再使用上面的背包策略就可以解决了。
这种带权重的求和的最优化问题,都可以转换为数组求和最优问题,(转化为判别划分问题)。
从具体的解法上来说,解法3,即公正陪审团问题的解法比较完善,可以保存路径,但是需要额外判断选取的某个数是否已经存在。且这种解法比较容易理解:
dp[k][s]:
外循环迭代k,表示取元素的个数;
中间循环迭代s:表示状态和s(限制条件,不能超过多少……)
内循环迭代index:表示具体是否选取A[index];
判别:+A[index]满足最优条件 &A[index]没有出现过(通过Path判别,保存)
最终:输出时若有个数限制K,则在dp[K][]中查找,若没有个数限制,则在dp[][]全部中查找
PS:利用Path输出路径时,可以先保存在set中,这样输出有序。
Read full article from 每日一题(19)——数组分割(动态规划) - 小熊不去实验室 - 博客频道 - CSDN.NET