Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Balo 3 nhánh cận

  1. #1
    Ngày gia nhập
    05 2008
    Nơi ở
    tx tra vinh
    Bài viết
    9

    Unhappy Balo 3 nhánh cận

    Bài toán BALÔ3, viết bằng kỷ thuật nhánh cận như sau:
    HÀM 1:
    C++ Code:
    1. //////////////////////////////////////////////////////////////////////////
    2.  int i_chay = 0;
    3.  // truyen tham so cho ROOT: tgt_cha = 0, w_cha = balo.trL, get_DT = 0, list_dd_cha = "chua di dau het
    4.  int nhanhCan( int tgt_cha, int w_cha, int get_DT, int *list_dd_cha)
    5.  {
    6.              printf("\n\n\nGia tri truyen vao: %d  %d  %d  %.2f\n", tgt_cha, w_cha, get_DT, DATA[listBB[get_DT]].dGi);
    7.     int *list_this, getDT_next = notUse;
    8.     int tgt = 0, w = 0;
    9.     list_this = new int [i_BD];
    10.     //thuc hien song bo list cha voi list hien tai
    11.     for ( int i=0; i< i_BD; ++i)
    12.         list_this[i] = list_dd_cha[i];
    13.     float ct = 0;
    14.     //xac dinh co phai nut la ko
    15.     int isLa = 0;
    16.     for (i=0; i<i_BD; ++i)
    17.         if (list_this[i] == notUse)
    18.             isLa++;
    19.         //neu isLa == 0 |==> chua thanh phan nao dung den het
    20.     for ( i = 0; i< i_BD; ++i)
    21.     {
    22.         tgt = w = 0;
    23.         if( kbhit()) return 0;
    24.         tgt = tgt_cha + DATA[i].gTr;
    25.         w = w_cha - DATA[i].trL;
    26. /*kiem tra*/    printf("\ntgt = %d, w = %d, trL = %d, gTr = %d", tgt, w, DATA[i].trL, DATA[i].gTr);
    27.        
    28.        
    29. /////////////////////////////////////////////////////////////////////////
    30.         if ( w < 0)
    31.             continue;
    32.         else if ((isLa == 0) && ( tgt > TGT) && ( w >= 0))
    33.         {          
    34.             TGT = tgt;
    35.             W = w;
    36.  /**/       printf("\n*****************************\n* Day la nut la temp: %d\t%d  *\n*****************************",TGT,
    37.  
    38. W);
    39.             i_KQ = i_chay;
    40.             for ( i=0; i<i_BD; ++i)
    41.                 listKQ[i] = list_this[i];
    42.             return -1;
    43.         }
    44.         else if( (w >= 0) && ( list_this[i] == notUse))// thuc hien phan nhanh nut nay
    45.         {
    46.             // danh dau
    47.             list_this[i] = isUse;
    48.             // thuc hien tinh ct_next cho this
    49.             for( i=0; i< i_BD; ++i)
    50.                 if ( list_this[i] == notUse)
    51.                 {
    52.                     getDT_next = i;
    53.                     break;
    54.                 }
    55.             ct = (float)tgt + (float)w * DATA[listBB[getDT_next]].dGi;
    56.  /*kiem tra*/       printf("\nCT = %.2f\tTEN: %s", ct, DATA[listBB[getDT_next]].ten);
    57.             // so sanh voi TGT
    58.             if ( ct<TGT)
    59.                 continue;
    60.             else
    61.             {
    62.                 i_chay++;
    63.  /*kiem tra*/           printf("\nDe quy!!!");
    64.                 nhanhCan( tgt, w, getDT_next, list_this);
    65.                 i_chay--;
    66.             }
    67.         }
    68.     }
    69.     return 0;
    70.  }
    71.  
    72.  
    73.  /*mo ta list_dd:
    74.     _all nhung phan tu da chon list_dd[i] = -1
    75.     _chua chon list_dd[i] = stt( voi stt = 1->end)
    76.  */
    77. //////////////////////////////////////////////////////////////////////////


    HÀM 2:
    C++ Code:
    1.  int nhanhCan( int tgt_cha, int w_cha, int stt, int *list_dd/)
    2.  {
    3.     //bat buoc phai sap xep du lieu truoc khi sd nhanhCan
    4.  /**/printf("\ntgt_cha=%d  w_cha=%d  stt=%d", tgt_cha, w_cha, stt);
    5.     int tgt = 0, w = 0, stt_next = 0;
    6.     float ct = 0;
    7.     int list_this[max];
    8.  
    9.     for (int i=0; i<max; ++i)
    10.         if (list_dd[i] != wasUse)
    11.             list_this[i] = notUse;
    12.         else
    13.             list_this[i] = wasUse;
    14.     list_this[stt] = wasUse;         //?
    15.  //khai bao xong
    16.     printf("\ni_BB = %d", i_BB);
    17.     for ( i=0; i<i_BB; ++i)
    18.     {
    19.         // tinh toan cac gia tri
    20.         tgt = tgt_cha + DATA[listBB[i]].gTr;
    21.         w = w_cha - DATA[listBB[i]].trL;
    22.         printf("\ngTr=%d  trL=%d,  listBB[i] = %d", DATA[listBB[i]].gTr, DATA[listBB[i]].trL, listBB[i]);
    23.         printf("\ntgt = %d\tw = %d", tgt, w);
    24.         if ( w < 0 )
    25.         {
    26. //          printf("\nw = %d", w);
    27.             continue;
    28.         }
    29.  /*==================================================================*/
    30.         for( i=0; i<i_BB; ++i)
    31.         {
    32.             if(list_this[i] == notUse)
    33.             {
    34.                 stt_next = i;/*tim vi tri vat next, dung cho tinh ct*/
    35.                 printf("\n\t\t<found::%d", stt_next);
    36.                 break;
    37.             }
    38.             else
    39.                 stt_next = isLa;
    40.         }
    41.  /*==================================================================*/
    42.         if ( (stt_next == isLa) && ( tgt > TGT))
    43.         {
    44.             // day la nut la co dk OK I
    45.             TGT = tgt;
    46.             W = w;
    47.             printf("\n\nDay la nut la: %s\n\n", DATA[listBB[i]].ten);
    48.             printf("\n\t\t>%d<====>%d<", TGT, W);
    49.             // list duong di:: dong bo hoa voi listKQ
    50.  //         getch();
    51.             return 0;
    52.         }
    53.  /*==================================================================*/
    54.         else
    55.         {
    56.             ct = (float)tgt + (float)w * (float)DATA[stt_next].dGi;
    57.             printf("\nCT = %.2f", ct);
    58.             if ( ct<TGT)
    59.                 continue;
    60.             else
    61.             {
    62.                 printf("\n**********\nDe quy: %s\n**********", DATA[stt].ten);
    63.  
    64.                 nhanhCan( tgt, w, stt_next, list_this);
    65.                 return 0;
    66.             }
    67.         }  
    68.     }
    69.     return 0;
    70.  }




    HÀM 3:
    C++ Code:
    1. //////////////////////////////////////////////////////////////////////////
    2. int nhanhCan( int tgt_cha = 0, int w_cha = 0, int stt = 0)
    3. {
    4.     int tgt = 0, w = 0, stt_next = 0, i = 0, ii = 1;
    5.     float ct = 0;
    6.     printf("\ntgt-cha = %d, w-cha = %d, stt = %d", tgt_cha, w_cha, stt);
    7.     while( i++< soPhantu)
    8.     {
    9.         tgt = w = stt_next = 0;
    10.         if (listBB[i] == wasUse)
    11.             continue;
    12.         tgt = tgt_cha + DATA[listBB[i]].gTr;
    13.         w = w_cha - DATA[listBB[i]].trL;
    14.         printf("\ntgt = %d\tw = %d", tgt, w);
    15.         if( w<0) continue;
    16.         stt_next = listBB[i];
    17.         listBB[i] = wasUse;
    18.         for ( ii=0; ii< soPhantu; ++ii)
    19.             if (listBB[ii] == wasUse)
    20.                 continue;
    21.             else
    22.                 break;
    23.         //da co dc ii
    24.             int tmp = listBB[ii];
    25.             listBB[ii] = wasUse;
    26.         printf("\nii = %d", ii);
    27.         if ( (ii == soPhantu) && (tgt > TGT) && (w>=0))
    28.         {
    29.             printf("\n**********\nDay la nut la %s\n**********", DATA[listBB[i]].ten);
    30.             TGT = tgt;
    31.             W = w;
    32.             //dong do listBB voi listKQ
    33.             for ( int iii=0; iii< soPhantu; ++iii)
    34.                 listKQ[iii] = listBB[iii];
    35.         }
    36.         ct = tgt + w*DATA[listBB[ii]].dGi;
    37.         printf("\nct = %.2f", ct);
    38.         if ( ct>TGT)
    39.         {
    40.             printf("\n Thuc hien de quy. tgt = %d, w = %d, stt_next = %d", tgt, w, stt_next);
    41.             nhanhCan( tgt, w, stt_next);
    42.         }
    43.         listBB[i] = stt_next;
    44.         listBB[ii] = tmp;
    45.         printf("\n********************************************************");
    46.     }
    47.     getch();
    48.     return 0;
    49. }
    50. //////////////////////////////////////////////////////////////////////////



    KHAI BÁO + NHẬP LIỆU, IN:
    C++ Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <string.h>
    4. #include <ctype.h>
    5. #include <process.h>
    6. #define max    50
    7. #define notUse -2
    8. #define wasUse -1
    9. #define isLa   -3
    10. //////////////////////////////////////////////////////////////////////////
    11. struct node
    12. {
    13.     int trL, gTr;
    14.     char ten[10];
    15.     float dGi;
    16. };
    17. //////////////////////////////////////////////////////////////////////////
    18. //tao bang vecto anh xa vao mang DATA
    19. static int listBB[max], listBD[max], listKQ[max];
    20. static int  i_BB = 0,    i_BD = 0,    i_KQ = 0;// giong i_data
    21. static int soPhantu = 0;
    22. static node DATA[max];// chi tham khao den chu ko sua doi gi het
    23. // static int i_data = 0;// luu tru vi tri cc trong ds dac data
    24. static node balo;
    25. static int TGT = 0, W = 0; // luu tru gia tri cc tim dc
    26. FILE *f;
    27. static char tenfile[10] = "dt2.dt";
    28. static int list_dd_ROOT [max];
    29.  
    30.  
    31. //////////////////////////////////////////////////////////////////////////
    32. void In( int);
    33. //////////////////////////////////////////////////////////////////////////
    34. void reset()
    35. {
    36.     for(int i=0; i<max; ++i)
    37.     {
    38.         listBB[i] = listBD[i] = listKQ[i] = i;
    39.         list_dd_ROOT[i] = notUse;
    40.     }
    41. }
    42. //////////////////////////////////////////////////////////////////////////
    43. void Bubble( int kieu)// 0: bubble:listBD       !0:bubble:listKQ
    44. {
    45.     int i, j;
    46.     int tmp, get1, get2;
    47.     if ( kieu == 0)
    48.     {
    49.         for( i=0; i<max; ++i, listBB[i] = listBD[i]);
    50.         i_BB = i_BD;
    51.     }
    52.     else
    53.     {
    54.         for( i=0; i<max; ++i, listBB[i] = listKQ[i]);
    55.         i_BB = i_KQ;
    56.     }
    57.     for( i = 1; i <= i_BB; ++i)
    58.         for( j = i_BB; j > i-1; --j)
    59.         {
    60.             get1 = listBB[j];
    61.             get2 = listBB[j-1];
    62. //          printf("\n%d:%d\t\t%.2f\t:\t%.2f ", get1, get2, DATA[get1].dGi, DATA[get2].dGi);
    63.  
    64.             if( DATA[get1].dGi > DATA[get2].dGi)
    65.             {
    66. //              printf("\t<this\t%d::%d", listBB[j], listBB[j-1]);
    67.                 tmp = listBB[j];
    68.                 listBB[j] = listBB[j-1];
    69.                 listBB[j-1] = tmp;
    70. //              printf(" _^o^_ %d::%d", listBB[j], listBB[j-1]);
    71.             }
    72.         }
    73. }
    74.  
    75. //////////////////////////////////////////////////////////////////////////
    76. void docTay()
    77. {
    78.     printf ("\nNhap vao so do vat toi da: "); scanf("%d", &soPhantu);
    79.     printf ("Nhap vao trong luong balo: "); scanf("%d", &balo.trL);
    80.     for (int i=0; i< soPhantu; ++i)
    81.     {
    82.         printf ("\n*****************************");
    83.         printf ("\nDo vat thu %d:", i+1);
    84.         printf ("\n\tTEN:           "); scanf("%s", &DATA[i].ten);
    85.         printf ("\tTRONG LUONG:   ");   scanf("%d", &DATA[i].trL);
    86.         printf ("\tGIA TRI:       ");   scanf("%d", &DATA[i].gTr);
    87.         if (DATA[i].trL ==0)
    88.             DATA[i].dGi = 1;
    89.         else
    90.             DATA[i].dGi = (float)(DATA[i].gTr) / (float)(DATA[i].trL);
    91.     }
    92.     i_BD = soPhantu;
    93.     luuFile();
    94. }
    95.  
    96. //////////////////////////////////////////////////////////////////////////
    97. void In( int kieu = 0)//0:listBD       1:listBB, 2:listKQ
    98. {
    99.     int *list_tmp;
    100.     int i_list;
    101.     if ( kieu == 0)
    102.     {
    103.         list_tmp = listBD;
    104.         i_list   = i_BD;
    105.         printf("\n\t\t****************************************");
    106.         printf("\n\t\t*            SO LIEU BAN DAU           *");
    107.         printf("\n\t\t****************************************");
    108.     }
    109.     else if( kieu == 1)
    110.     {
    111.         list_tmp = listBB;
    112.         i_list   = i_BB;
    113.         printf("\n\t     ****************************************************");
    114.         printf("\n\t     *    SO LIEU SAU KHI DUNG HAM SAP XEP (BUBBLE)     *");
    115.         printf("\n\t     ****************************************************");
    116.     }
    117.     else
    118.     {
    119.         list_tmp = listKQ;
    120.         i_list   = i_KQ;
    121.         printf("\n\t\t****************************************");
    122.         printf("\n\t\t*               KET QUA                *");
    123.         printf("\n\t\t****************************************");
    124.         printf("\nTong trong luong con du: %d", W);
    125.         printf("\nTrong luong tim duoc:      %d", balo.trL - W);
    126.         printf("\nTong gia tri lay dc:     %d", TGT);
    127.         printf("\nBang:");
    128.     }
    129.     int get;
    130.     printf("\n-------------------------------------------------------------------------");
    131.     printf("\n|  STT\t|\tTEN\t|\tTRL\t|\tGTR\t|\tDGI\t|");
    132.     printf("\n-------------------------------------------------------------------------");
    133.     for (int i=0; i<i_list; ++i)
    134.     {
    135.         if( list_tmp[i] == wasUse) continue;
    136.         get = list_tmp[i]; //printf("%d:%d", get, listBD[i]);
    137.         printf("\n|   %d\t|\t%s\t|\t%d\t|\t%d\t|\t%.2f\t|", i+1, DATA[get].ten, DATA[get].trL, DATA[get].gTr,
    138.  
    139. DATA[get].dGi);
    140.     }
    141.     printf("\n-------------------------------------------------------------------------");
    142. }
    143. //////////////////////////////////////////////////////////////////////////





    Tất cả 3 hàm nhanhCan() trên đó, đều sai hết. Đệ viết đi viết lại gần tháng rưỡi rồi, mà chạy ko đúng. Mong các huynh giúp với.( có lẽ hàm 3 là đúng nhất).
    NỘI DUNG BÀI TOÁN BALO LÀ:
    Code:
        =>Cho 1 cái balo có thể chứa đc trọng lượng w ( ở trên là balo.trL), 1 siêu thị với những món đồ có tên ( ko quan trọng, ở trên là *DATA[i].ten), có trọng lượng là wi ( DÂT[i].trL), giá trị là vi ( DÂT[i].gTr). Có 1 tên trộm..... (gì đó). Yêu cầu bài toán là: Lấy các món đồ sao cho " hết chứa trong balo dc thì thôi" và tổng giá trị là lớn nhất.
    NỘI DUNG NHÁNH CẬN LÀ:
    Code:
    +Khởi đầu là nút RÔT biểu diễn cho việc chưa chọn món đồ vật nào hết.
    
    +Ứng với mỗi nút Tính( hết các con):
             *    TGT = tgt_cha + this->gTr;
             *    W = w_cha - this->trL;
             *    CT = TGT + W * next->dGi;( dGi vật sẽ xét tiếp theo)
    +Chọn nút có CT lớn nhất ==> đệ quy nó
    +Khi đi đến nút lá( ss với max_temp( lúc đầu == 0) nếu lớn hơn thì gán), ta quay lui.......( khó lắm a). S sánh max_temp.W voi CT nhung thang chua xet, thằng nào bé hơn thì cắt bỏ, lớn hơn thì đệ quy.
     ( khúc trên hơi lũng cũng, so sory).
    +Khi tất cả các nút đều đc phân nhánh, hoặc bị cắt tỉa hết, thì mac_temp là kq bài toán


    Còn cái du liệu là:
    balo 37
    a 15 30
    b 10 25
    c 2 2
    d 4 6




    Note: mấy hàm phụ thì ko có sai sót gì, chỉ là hàm nhanhCan() thôi
    Mọi lý thuyết đều màu xám, chỉ có cây đời mãi xanh tươi !!!

  2. #2
    Ngày gia nhập
    05 2008
    Nơi ở
    tx tra vinh
    Bài viết
    9

    trời ơi sao ko có ai hướng dẫn giùm hết vậy.
    Mọi lý thuyết đều màu xám, chỉ có cây đời mãi xanh tươi !!!

Các đề tài tương tự

  1. Balo Laptop The North Face
    Gửi bởi yamekd92 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 23-02-2012, 10:01 PM
  2. Bài toán Balo bằng phương pháp Quy hoạch động
    Gửi bởi Qh1988 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 16-02-2011, 08:54 PM
  3. Bài toán balo | Sắp xếp đồ vật đầy balo bằng vét cạn
    Gửi bởi thanhluan710 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 03-11-2010, 05:52 PM
  4. Bài toán cái balo
    Gửi bởi luutruonghailan trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 23-03-2009, 06:55 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn