以下是lowai的程序,牛啊,学习中。
#include <stdio.h>
#include <stdlib.h> //due to:qsort
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
int stick[100];
int total;
int ns; //一共需要还原出的木棍数ns
int ok;
int len; //当次需要达到的长度
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int cmp(const void *a,const void *b)
{
int a1 = *(int *)a;
int a2 = *(int *)b;
return a2 - a1;
}
int used[100];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int adds()
{
int j = 0;
for (int i = 1;i <= n;i++)
j += stick[i];
return j;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void search(int,int,int);
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void s(int x)
{ //x 正在还原第x根木棍
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (x > ns)
{
ok = 1;
printf("%d\n", len);
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i;
for (i = 1;i <= n;i++)
if (!used[i]) break; //找到第一根没有使用的木棍
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
used[i] = 1; //改变它的使用状态
search(x,stick[i],i); //搜索
used[i] = 0; //还原它的使用状态
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void search(int num,int now,int next)
{ //num正在还原第num根木棍
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (ok) return;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (now == len)
{ //一根木棍还原完
s(num + 1); //还原下一根
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if (next + 1 > n) return; //总共只有n根短棍
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (int i = next + 1;i <= n;i++)
if (!used[i])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(stick[i] + now <= len)
{ //该木棍加上当前长度小于len
used[i] = 1;
search(num,now + stick[i],i); //搜索
used[i] = 0;
if (ok) return;
if (stick[i] == len - now) return; //有一根木棍长度正好等于当前差值
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main ()
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (scanf("%d", &n) == 1)
{
if (!n) break; //读数据
ok = 0;
int i;
for (i = 1;i <= n;i++) scanf("%d", &stick[i]);
qsort(stick+1,n,sizeof(int),cmp); //快速排序,从大到小
total = adds(); //计算木棍总长度
for (i = stick[1];i <= total;i++) //从最大的木棍 到 总长度 ,依次枚举
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (total % i == 0 && !ok)
{ //如果该长度可以被总长度整除,且还没有ok
ns = total / i; //求出一共需要还原出的木棍数ns
memset(used,0,sizeof(used)); //所有木棍使用状态清零
len = i; //当次需要达到的长度
s(1);
}
}
return 0;
}
另外,stdlib.h中的qsort还是挺好用的,呵呵