「箱詰め」問題の貪欲な解決アルゴリズム

/*
      ：<<     >>      -[        ]
      ：   
      ：2002 09 14 (18:20:00-20:18:00)
            “  ”           
      ：2002 09 14 (22:00:00-23:18:00)
            “  ”           
      ：2002 09 14 (18:20:38-22:18:00)
            “     ”          
*/
#include    "stdio.h"
#include    "stdlib.h"

//:============================“  ”          ===========================
/*
      ：   
      ：2002 09 14 (18:20:38-20:00:00)
            “  ”          
    ===================================================
        :
                 0,1,2,...,n-1 n   ,     v0,v1,v2,...,vn-1,
          n         V       。   n          
        V,   0<=i<n, 0<v_i<=V。           n   。

        :
                            ，               ，
                                    。
        :
    {
               ;
                ;
                           ;
                 ;
                 box_count 0;
        for(i=0;i<n;i++)
        {//  i       ;
                                i   j;
            if(           i)
            {
                      ,    i      ;
                box_count ++;
            }
            else
                   i    j ;
        }
    }

*/
//          
#define        RES        struct    RES
RES
{
    int    order;        //    
    RES * link;        //        
};
//          
#define        BOX        struct    BOX
BOX
{
    int    remainder;    //      
    RES    *r_head;    //               
    BOX    *link;        //            
};
void    Encase_Box()
{
    //     ,    ,    ,     
    int    box_count,box_volume,category,i;
    int    *array;        //               
    //        、     ,          
    BOX    *b_head,*b_tail,*box;
    RES    *p_res,*q_res;        //          ,                  

    printf("       ：	");
    scanf("%d",&box_volume);
    printf("       ：	");
    scanf("%d",&category);
    array = (int *)malloc(category * sizeof(int));
    printf("                 ： ");
    for(i=0;i<category;i++)
    {
        printf("  [%d]    = 	",i+1);
        scanf("%d",array + i);
    }
    b_head = b_tail = NULL;        //          
    box_count = 0;                //         
    for(i=0;i<category;i++)
    {//  i       
        // [   ]                i   j;
        p_res = (RES *)malloc(sizeof(RES));
        p_res->order = i;
        p_res->link = NULL;
        for(box = b_head;box != NULL;box = box->link)
        {
            if(box->remainder >= array[i])
                break;        //        i   [box     ]
        }
        if(box == NULL)
        {//           i,       
            //              i
            box = (BOX *)malloc(sizeof(BOX));
            box->remainder = box_volume - array[i];    //          
            box->link = NULL;
            box->r_head = NULL;        //           
            if(b_head == NULL)
                b_head = b_tail = box;    //                  
            else
                b_tail = b_tail->link = box;    //                         
            box_count ++;    //         
        }
        else
            box->remainder = box->remainder - array[i];    //   i      box 
        //  11 :   i       box        
        //   q_res：                   
        for(q_res = box->r_head;q_res != NULL && q_res->link != NULL;q_res = q_res->link);
        if(q_res == NULL)
        {//        ,    i     box       
            p_res->link = box->r_head;    //  i link  NULL
            box->r_head = p_res;        //   box               p_res
        }
        else
        {
            p_res->link = NULL;            //  i link  NULL
            q_res->link = p_res;        //  i       box       q_res  
        }
    }
    //           
    printf("    [%d]   [%d]      [%d]   ！",box_volume,box_count,category);
    printf("           ： ");
    for(box = b_head,i=1;box != NULL;box = box->link,i++)
    {// i         
        printf(" %2d   ，     %4d，     : ",i,box->remainder);
        for(p_res = box->r_head;p_res != NULL;p_res = p_res->link)
            printf("	   [%d],    [%d] ",p_res->order + 1,array[p_res->order]);
        printf(" ");
    }
}
//:============================“  ”          ===========================

int main(int argc, char* argv[])
{
    //Encase_Box();
    //Journey_Horse();
    Run_Give_Change();
    printf("         ！ ");
    return 0;
}