动态规划7-正整数分组
时间： 09:09:03
&&&& 阅读：828
&&&& 评论：
&&&& 收藏：0
标签：将一堆正整数分为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的情况是否可能出现。
考虑一下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值。
那么我们有别的方法么？考虑最后分组情况，如果所有数的和为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(n, [sum / 2])。时间复杂度和空间复杂度依然是O(n * [sum / 2]) ，同样可以优化掉一维的空间复杂度。综上所述，两种方法的时间复杂度都是O(n * sum)级别的，通常sum不是很大，比如说本题sum不超过10000，所以从实际角度上讲，这个复杂度比O(2n)强多了。再顺带说一下如果要求出一组最优解的具体分配方案，怎么做？
别忘了，动态规划问题，求具体方案的惯用方法就是记录当前f(i,j)是由之前哪个状态得到的，然后一步一步小心谨慎地回退到起点，就像我们在搜索问题中记录之前地节点恢复出路径一样。
最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。
第1行：一个数N，N为正整数的数量。
第2 - N+1行，N个正整数。
(N &= 100, 所有正整数的和 &= 10000)
输出这个最小差
1 #正整数分组
2 n=int(input())
6 for i in range(n):
x=int(input())
a.append(x)
f.append(0)
11 k=int(sum / 2)
12 for i in range(k):
f.append(0)
14 for i in range(1,n+1):
for j in range(k,a[i]-1,-1):
f[j]=max(f[j],f[j-a[i]]+a[i])
17 print(sum-2*f[k])
&&国之画&&&& &&&&chrome插件&&
版权所有 京ICP备号-2
迷上了代码！#include&stdio.h&int main(){ int m,n,i,line[104],s,j,h; int
aver1,aver2; while(scanf("%d%d",&n,&m)!=EOF) {
line[0]=2;
for(i=1;i&n;i++)
line[i]=line[i-1]+2;
for(j=0;j&n/m;j++)
for(i=j*m;i&(j+1)*m;i++)
s=line[i]+s;
aver1=s/m;
printf("%d",aver1);
else printf(" %d",aver1);
for(i=n-h;i&n;i++)
s=s+line[i];
aver2=s/h;
printf(" %d",aver2);
printf("\n"); } return 0; }
阅读(...) 评论()查看: 266|回复: 9
输入两正整数m和n（m≥1n≤1000）输出mn之间所有水仙花数?水仙花数指各位数字立方和等于其自身数?例153各位数字立方和13+53+33 =153?求解我段代码底哪里错了#includeint main(void){& & & & int m,n,i,j,sum=0,a;& & & & printf(&Input m: &);& & & & scanf(&%d&,&m);& & & & printf(&Input n: &);& & & & scanf(&%d&,&n);& & & & for(i=m;i
非著名人士
#include #include int main(void) { int m,n,i,sum,a; printf(&Input m: &); scanf(&%d&,&m); printf(&Input n: &); scanf(&%d&,&n); // for(i=m;i
//你既然连main函数也给忘了，主要1000也要排除 #include #include int main() { int i,m,n,x,y,z; printf(&Inpu m:&); scanf(&%d&,&m); printf(&Input n:&); scanf(&%d&,&n); for(i=m;i
仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n 次幂之和等于它本身。（例如：1^3 + 5^3 + 3^3 = 153）这是百度百科对水仙花数的定义。 求小于100的数的水仙花数是没有什么意义的。因为1到9水仙花数就是它本身。而两位数是没有水仙花数...
受了伤的农民
随便拿一个正整数，我想假如模10大于0的话，再模无数遍也是大于零的，所以你里面那个循环果断悲剧。
啥意思？似乎很简单的问题，程序写的太差了，我给你重写。。 就是输出m,n之间的整数还是？
is(i);printf(&%d\n&);// 修改为: if (is(i)){ printf(&%5d&, i);} 即，判断到是水仙花数的才需要输出，要加 if 判断 另外，if(number==i*i*i+j*j*j+k*k*k) 也需要修改一下 if (number == i * i * i + j * j * j + k * k * k){ r...
/* low = 1 high = 9999 1是水仙花数。 1的各位数字之和与其自身相等。 2的各位数字之和与其自身相等。 3的各位数字之和与其自身相等。 4的各位数字之和与其自身相等。 5的各位数字之和与其自身相等。 6的各位数字之和与其自身相等。 7的各位数...
factorsum函数定义有误，里面的a与之前的a可能有冲突，换个名称试试。
天之，骄子
#include int shuixianhua(int m) { int s=0,flag=0,a,b,c; a=m/100; c=m%10; b=m/10%10; s+=a*a*a+b*b*b+c*c* if(s==m) flag=1; return(flag); } main() { for(i=1;i}