POJ 1011 Sticks CODE[VS] 3498 작은 나무 막대기(DFS+ 가지치기 최적화)

가지치기 신제CODE[VS]3498은 한 조의 데이터에 불과하지만 마지막에 0이 없습니다 = =나무 막대 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 139356 Accepted: 32861 Description
조지는 각각의 길이가 50개의 길이 단위를 넘지 않도록, 등길이의 나무 막대기를 가져와 무작위로 잘랐다.그리고 나서 그는 이 나무 막대기를 자르기 전의 상태로 회복하고 싶었지만, 처음에는 얼마나 많은 나무 막대기와 나무 막대기의 초기 길이가 있었는지 잊어버렸다.조지가 나무 막대기의 최소 길이를 계산할 수 있도록 프로그램을 설계해 주십시오.각 막대기의 길이는 0보다 큰 정수로 표시한다.Input
입력은 여러 그룹의 데이터를 포함하고, 한 그룹의 데이터는 두 줄을 포함한다.첫 번째 줄은 64를 넘지 않는 정수로 잘라낸 후 모두 몇 개의 나무 막대기가 있는지 나타낸다.두 번째 줄은 절단 후 얻은 각 막대기의 길이다.마지막 조의 데이터 뒤에는 0이 있다.Output
각 조의 데이터를 위해 원시 나무 막대기의 최소 길이를 각각 출력하고 각 조의 데이터는 한 줄을 차지한다.Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0 Sample Output
6 5
아주 좋은 가지치기 최적화 연습문제 해법: DFS+가지치기는 다음과 같다.다음 긴 막대기를 검색할 때, 첫 번째 아직 사용하지 않은 작은 막대기를 찾기 시작하면, 순서가 정해져 있기 때문에, 첫 번째 막대기가 가장 길고, 반드시 사용해야 하기 때문에 다음 막대기부터 검색하기 시작한다.
2. 앞뒤 두 길이가 같을 때 앞의 뿌리가 사용되지 않으면 앞의 뿌리부터 정확한 결과를 찾지 못하면 다시 이 뿌리부터 정확한 결과를 찾지 못할 것이다
3. 큰 막대기로 맞추려면 필요한 길이 L>= 현재 작은 막대기의 길이를 선택해야 합니다
4. 이번의 작은 막대기는 남은 길이를 채우기 딱 좋은데 뒤의 검색이 실패하면 윗층으로 돌아가야 한다
코드는 다음과 같습니다.

#include 
#include 
#include 
#include  
using namespace std;
const int size=10010;
int num[size],n,sum;
bool used[size];
int cmp(int x,int y) {return x > y;}
 //tot   ，unused      rml             len        
bool dfs(int tot,int unused,int rml,int len)
{
    if(unused == 0 && rml == 0)  return true;
    //       0，     0，    
    if(rml == 0) rml = len;
     //           0            
    for(int i = 1;i <= tot; i ++)//             
    {
        if(used[i] == true) continue;
        //        
        if(num[i] > rml) continue; 
        //                   
        used[i] = true;       
        if(dfs(tot,unused-1,rml-num[i],len)==true) return true;
        //         
        used[i] = false;
         //        
        if(num[i] == rml || rml == len) break;
        //                                     
    }
    return false;
}

void init() 
{
    memset(num,0,sizeof(num));
    memset(used,0,sizeof(used));
    sum = 0;
}
int main()
{
//  while (scanf("%d",&n))
//  {
        scanf("%d",&n);
        if(n == 0) return 0; 
        init();
        for(int i = 1;i <= n;i ++)
        {
            scanf("%d",&num[i]);
            sum += num[i];
        }
        sort(num + 1,num + n + 1,cmp);
        for(int i = num[1];i <= sum;i ++)
        {
            if(sum % i == 0)
            if(dfs(n,n,0,i) == true)
            {
                printf("%d
",i);
                break;
            }
        }
//  }
    return 0;
}

가지치기 하니까 헷갈리네요. QAQ 본인이 이 코드를 좀 더 알아봐야 될 것 같아요. 채팅도 좀 더 해야 될 것 같아요. 힘내요, QAQ.