附上代碼,裡面有注釋! 0MS!
[cpp]
#include <stdio.h>
#include <stdlib.h>
int sticks[64];
int used[64];
int stick_num=0;
int target_num =0;
int target_length=0;
int run_time;
int compare(const void *a, const void *b)
{
return *((int*)b)-*((int*)a);
}
int search(int stick_index,int left, int cur_index)
{
//如果成功配對一根
if(left == 0)
{
if(stick_index == target_num-1)
return 1;
stick_index++;
for(cur_index=1;used[cur_index]==1;cur_index++)
;
left = target_length;
used[cur_index]=1;
if(search(stick_index,left-sticks[cur_index],cur_index+1) == 1)
return 1;
used[cur_index]=0;
return 0;
}
else
{
int i=0;
for(i=cur_index;i<stick_num;i++)
{
if(used[i]==0 && sticks[i]<=left)
{
if(used[i-1]==0 && sticks[i]== sticks[i-1]) //剪枝1,重要
continue;
run_time++ ;
used[i] = 1;
if(search(stick_index,left-sticks[i],i+1) == 1)
return 1;
used[i] = 0;
if(sticks[i] == left || left == target_length) //剪枝2、3,重要
{
return 0;
}
}
}
return 0;
}
}
int main()
{
int n = 0;
int sum;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
sum = 0;
int i=0;
int max=0;
stick_num = n;
for(i=0;i<n; ++i)
{
scanf("%d",&sticks[i]);
sum += sticks[i];
if(sticks[i]>max)
max = sticks[i];
}
memset(used,0,sizeof(used));
qsort(sticks,n,sizeof(int),compare); //優化數組,減少搜索次數
for(i=stick_num;i>0;i--)
{
if(sum%i == 0 &&(sum/i)>=max)
{
target_num = i;
target_length = sum/i;
run_time = 0;
used[0] = 1;
if(search(0,target_length-sticks[0],1))
{
//printf("run %d times, %d\n",run_time,target_length);
printf("%d\n",target_length);
break;
}
}
}
}
return 0;
}