算法分析与设计第三章（清华大学出版社）划分问题：（用动态规划）现提供已经数据：30个元素a[]={21,5,38,11,10,17,15,27,25,42,22,8,26,13,16,37,1,24,31,19,2,14,28,3,33,23,43,20,12,14};要求：输入：A={a1,a2,…,an},其中ai∈Z+(1≤i≤n)输出：是否存在P属于A,使∑ai=∑aj (ai∈P,aj∈A-P)要求用C语言做
热心网友
一、为什么用动态内存分配 但我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0。5分）数组：float score[30]; 但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？ 在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。 那么有没有其它的方法来解决这样的外呢体呢？有，那就是动态内存分配。 所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。从以上动、静态内存分配比较可以知道动态内存分配相对于景泰内存分配的特点： 1、不需要预先分配存储空间； 2、分配的空间可以根据程序的需要扩大或缩小。 二、如何实现动态内存分配及其管理 要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数 1、malloc函数 malloc函数的原型为：void *malloc (unsigned int size) 其作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。 下例是一个动态分配的程序：#include#includemain(){ int count,*array; /*count是一个计数器，array是一个整型指针，也可以理解为指向一个整型数组的首地址*/ if((array(int *) malloc(10*sizeof(int)))==NULL) { printf("不能成功分配存储空间。"); exit(1); } for (count=0;count〈10;count++) /*给数组赋值*/ array[count]=count; for(count=0;count〈10;count++) /*打印数组元素*/ printf("%2d",array[count]);} 上例中动态分配了10个整型存储区域，然后进行赋值并打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)语句可以分为以下几步： 1）分配10个整型的连续存储空间，并返回一个指向其起始地址的整型指针 2）把此整型指针地址赋给array 3）检测返回值是否为NULL 2、free函数 由于内存区域总是有限的，不能不限制地分配下去，而且一个程序要尽量节省资源，所以当所分配的内存区域不用时，就要释放它，以便其它的变量或者程序使用。这时我们就要用到free函数。 其函数原型是：void free(void *p) 作用是释放指针p所指向的内存区。 其参数p必须是先前调用malloc函数或calloc函数（另一个动态分配存储区域的函数）时返回的指针。给free函数传递其它的值很可能造成死机或其它灾难性的后果。 注意：这里重要的是指针的值，而不是用来申请动态内存的指针本身。例：int *p1,*p2;p1=malloc(10*sizeof(int));p2=p1;……free(p2) /*或者free(p2)*/ malloc返回值赋给p1，又把p1的值赋给p2，所以此时p1，p2都可作为free函数的参数。 malloc函数是对存储区域进行分配的。 free函数是释放已经不用的内存区域的。 所以由这两个函数就可以实现对内存区域进行动态分配并进行简单的管理了。
热心网友
仅提供思路，程序还是要你自己写：先把这30个数加起来，如果是奇数肯定不存在，如果是偶数，就有可能。设2个集合S，T（S交T等于空集，S并T等于全集）1。先放两个元素（数组的头两个元素），以楼主数据为例， 21和5，分别放在S和T中。再在剩下的N-2个元素里寻找16，因为21-5=16（即两个集合和的差值），如果找到了，就将16放入T，取下两个没有取到的元素38和11。重复步骤1。否则，没找到使两个集合元素和相等的数，做步骤2。2。没有的话取最接近16的数放入T。然后比较两个集合元素和的差值，每次都取最接近差值但小于差值的数放入和小的那个集合，直到差值为零再取下两个没有被去过的元素。即回到步骤1在每一次取数后检查是否所有数都被取遍（即T和S集合的元素数目之和是否等于原来全集元素数）如都被取遍就跳出，此时若两集合元素和不相等说明不存在这样的P使使∑ai=∑aj (ai∈P,aj∈A-P)。