首页 > 代码库 > 动规讲解基础讲解八——正整数分组
动规讲解基础讲解八——正整数分组
将一堆正整数分为2组，要求2组的和相差最小。
例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。 整数个数n<=100，所有整数的和<=10000
初看题目，第一想到贪心。怎么贪？排序，每次把数放到“最有利”的一边，最有利指的是每次都把数放到使得结果差值尽可能小的那边。这样的方法显然前两个数只能分到不同的组了，这是不对的。比如{1,2,3}，这种贪心会把1和2分开，显然得不到最优解。 最优解是{1,2}在一起，3自己在一组。
是不是如果找到一个数和其他几个数的和相等，就一定先把这个数和另外那几个数分开放？因为这样放差值仍然是0。 不是的，看看{1,2,3,7}，我们不能把{1,2}和3分开。而是应该{1,2,3}一起放到一组才最优。
没招了。万能的枚举啊，我们把每个数要么放第一组，要么放第二组，所以一共2^n种情况，取一种差值最小的就好了。这种方法固然可以，但是实际复杂度太高了。
继续枚举的思路，我们为什么要尝试那么多情况呢？因为我们在决定第i个数放到哪组的时候，前面的所有2^i-1种情况可能产生的两组数可能有不同的差值。对！关键因素不在于前面的2^i-1种情况，而在于差值的情况。
那么，我们用bool f(i,j)表示前i个数分成两组，差值是j的情况是否可能出现。
例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。 整数个数n<=100，所有整数的和<=10000
初看题目，第一想到贪心。怎么贪？排序，每次把数放到“最有利”的一边，最有利指的是每次都把数放到使得结果差值尽可能小的那边。这样的方法显然前两个数只能分到不同的组了，这是不对的。比如{1,2,3}，这种贪心会把1和2分开，显然得不到最优解。 最优解是{1,2}在一起，3自己在一组。
是不是如果找到一个数和其他几个数的和相等，就一定先把这个数和另外那几个数分开放？因为这样放差值仍然是0。 不是的，看看{1,2,3,7}，我们不能把{1,2}和3分开。而是应该{1,2,3}一起放到一组才最优。
没招了。万能的枚举啊，我们把每个数要么放第一组，要么放第二组，所以一共2^n种情况，取一种差值最小的就好了。这种方法固然可以，但是实际复杂度太高了。
继续枚举的思路，我们为什么要尝试那么多情况呢？因为我们在决定第i个数放到哪组的时候，前面的所有2^i-1种情况可能产生的两组数可能有不同的差值。对！关键因素不在于前面的2^i-1种情况，而在于差值的情况。
那么，我们用bool f(i,j)表示前i个数分成两组，差值是j的情况是否可能出现。
考虑一下f(i,j)的含义我们把第i个数放到了某一组，差值变成了j (j >= 0)
第i个数放入哪个组有两种可能：
（1） 第i个数放入原来和比较大的组，那么放入第i个数的时候差值变成了j，拉大了差值，所以原来的差值是j - ai (j >=ai),那么如果f(i-1, j - ai)是true，则f(i,j)也为true
（2） 第i个数放入原来和比较小的组，那么放入第i个数的时候又有两种情况：
（2.1） 原来相差很大了，已经是j + ai了，加入ai缩小了差距，于是意味着如果f(i－ 1， j + ai) ＝ true，则f(i,j)是true。
（2.2） 原来相差不大， 加入ai之后，和较小的组变成了和较大的组。那么原来大的比小的和大ai – j （ai >=j), 于是意味着如果f(i – 1, ai – j)是true，则f(i,j)为true。
（1）和(2.2)可以统一成若 f(i-1, |j - ai|) = true，则f(i,j) = true
总结前面说的
f(i,j) = f(i – 1, |j - ai|) || f(i – 1, j + ai)
这里我们巧妙地运用绝对值和逻辑或运算。
继续考虑，初值是什么？ f(0,0) = true。没有数的时候，差值只能是0，其余f(0,x > 0) = false。
第二维有多大？ 第二维大小可以达到所有数的所以时间复杂度是O(n * sum),空间复杂度也是 O(n * sum)，这里sum是所有数的总和。
最终答案是什么？
根据定义，最终答案是min{x| f(n,x) = true}
空间优化？ f(i, *)只与f(i – 1, *)有关，所以两行，达到递推的目的。
上面的解法看起来不是动态规划，因为动态规划的式子看起来应该是个“优化”问题，也就是应该有max或者min的样子，而不是一个bool值。
第i个数放入哪个组有两种可能：
（1） 第i个数放入原来和比较大的组，那么放入第i个数的时候差值变成了j，拉大了差值，所以原来的差值是j - ai (j >=ai),那么如果f(i-1, j - ai)是true，则f(i,j)也为true
（2） 第i个数放入原来和比较小的组，那么放入第i个数的时候又有两种情况：
（2.1） 原来相差很大了，已经是j + ai了，加入ai缩小了差距，于是意味着如果f(i－ 1， j + ai) ＝ true，则f(i,j)是true。
（2.2） 原来相差不大， 加入ai之后，和较小的组变成了和较大的组。那么原来大的比小的和大ai – j （ai >=j), 于是意味着如果f(i – 1, ai – j)是true，则f(i,j)为true。
（1）和(2.2)可以统一成若 f(i-1, |j - ai|) = true，则f(i,j) = true
总结前面说的
f(i,j) = f(i – 1, |j - ai|) || f(i – 1, j + ai)
这里我们巧妙地运用绝对值和逻辑或运算。
继续考虑，初值是什么？ f(0,0) = true。没有数的时候，差值只能是0，其余f(0,x > 0) = false。
第二维有多大？ 第二维大小可以达到所有数的所以时间复杂度是O(n * sum),空间复杂度也是 O(n * sum)，这里sum是所有数的总和。
最终答案是什么？
根据定义，最终答案是min{x| f(n,x) = true}
空间优化？ f(i, *)只与f(i – 1, *)有关，所以两行，达到递推的目的。
上面的解法看起来不是动态规划，因为动态规划的式子看起来应该是个“优化”问题，也就是应该有max或者min的样子，而不是一个bool值。
那么我们有别的方法么？
考虑最后分组情况，如果所有数的和为sum, 较小和的那组数一定不超过 [sum / 2]。我们的目标是使得和较小组的总和尽可能大。
我们的目标是从这n个数中选出一些数，这些数的总和不超过[sum / 2]且总和尽可能大。
那我们重新定义int f(i,j)表示从前i个数中选出的数，总和不超过j的时候能得到的最大的和。
则如果不选择ai f(i-1,j) = f(i,j)
如果选择ai,则f(i,j) = f(i, j - ai) j >= ai
第二维大小是[sum / 2]
初值是f(0, x) = 0 注意含义是总和“不超过”x的时候的最大值。
递推式是
f(i,j)={ f(i−1,j)(j<ai)
考虑最后分组情况，如果所有数的和为sum, 较小和的那组数一定不超过 [sum / 2]。我们的目标是使得和较小组的总和尽可能大。
我们的目标是从这n个数中选出一些数，这些数的总和不超过[sum / 2]且总和尽可能大。
那我们重新定义int f(i,j)表示从前i个数中选出的数，总和不超过j的时候能得到的最大的和。
则如果不选择ai f(i-1,j) = f(i,j)
如果选择ai,则f(i,j) = f(i, j - ai) j >= ai
第二维大小是[sum / 2]
初值是f(0, x) = 0 注意含义是总和“不超过”x的时候的最大值。
递推式是
f(i,j)={ f(i−1,j)(j<ai)
{ max(f(i−1,j),f(i,j−ai)+ai)(ai<=j<=[sum/2])
那么最终答案是什么？ 根据定义，应该是f(n, [sum / 2])。
时间复杂度和空间复杂度依然是O(n * [sum / 2]) ，同样可以优化掉一维的空间复杂度。
综上所述，两种方法的时间复杂度都是O(n * sum)级别的，通常sum不是很大，比如说本题sum不超过10000，所以从实际角度上讲，这个复杂度比O(2n)强多了。
再顺带说一下如果要求出一组最优解的具体分配方案，怎么做？
别忘了，动态规划问题，求具体方案的惯用方法就是记录当前f(i,j)是由之前哪个状态得到的，然后一步一步小心谨慎地回退到起点，就像我们在搜索问题中记录之前地节点恢复出路径一样。
题解：
#include <iostream> #include<bits/stdc++.h> using namespace std; int d[11000],a[10100]; int main() { int n; scanf("%d",&n); int sum=0; for(int i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } int m=sum/2; memset(d,0,sizeof(d)); for(int i=0;i<n;i++) for(int j=m;j>=a[i];j--) d[j]=max(d[j],d[j-a[i]]+a[i]); cout<<sum-2*d[m]<<endl; }
如果对你有所帮助，别忘了加好评哦；么么哒！！下次见！88
动规讲解基础讲解八——正整数分组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。