Bài toán BALÔ3, viết bằng kỷ thuật nhánh cận như sau:
HÀM 1:
Mã:
////////////////////////////////////////////////////////////////////////// int i_chay = 0; // truyen tham so cho ROOT: tgt_cha = 0, w_cha = balo.trL, get_DT = 0, list_dd_cha = "chua di dau het int nhanhCan( int tgt_cha, int w_cha, int get_DT, int *list_dd_cha) { printf("
Gia tri truyen vao: %d %d %d %.2f
", tgt_cha, w_cha, get_DT, DATA[listBB[get_DT]].dGi); int *list_this, getDT_next = notUse; int tgt = 0, w = 0; list_this = new int [i_BD]; //thuc hien song bo list cha voi list hien tai for ( int i=0; i< i_BD; ++i) list_this[i] = list_dd_cha[i]; float ct = 0; //xac dinh co phai nut la ko int isLa = 0; for (i=0; i<i_BD; ++i) if (list_this[i] == notUse) isLa++; /eu isLa == 0 |==> chua thanh phan nao dung den het for ( i = 0; i< i_BD; ++i) { tgt = w = 0; if( kbhit()) return 0; tgt = tgt_cha + DATA[i].gTr; w = w_cha - DATA[i].trL;/*kiem tra*/ printf("
tgt = %d, w = %d, trL = %d, gTr = %d", tgt, w, DATA[i].trL, DATA[i].gTr); ///////////////////////////////////////////////////////////////////////// if ( w < 0) continue; else if ((isLa == 0) && ( tgt > TGT) && ( w >= 0)) { TGT = tgt; W = w; /**/ printf("
*****************************
* Day la nut la temp: %d\t%d *
*****************************",TGT, W); i_KQ = i_chay; for ( i=0; i<i_BD; ++i) listKQ[i] = list_this[i]; return -1; } else if( (w >= 0) && ( list_this[i] == notUse))// thuc hien phan nhanh nut nay { // danh dau list_this[i] = isUse; // thuc hien tinh ct_next cho this for( i=0; i< i_BD; ++i) if ( list_this[i] == notUse) { getDT_next = i; break; } ct = (float)tgt + (float)w * DATA[listBB[getDT_next]].dGi; /*kiem tra*/ printf("
CT = %.2f\tTEN: %s", ct, DATA[listBB[getDT_next]].ten); // so sanh voi TGT if ( ct<TGT) continue; else { i_chay++; /*kiem tra*/ printf("
De quy!!!"); nhanhCan( tgt, w, getDT_next, list_this); i_chay--; } } } return 0; } /*mo ta list_dd: _all nhung phan tu da chon list_dd[i] = -1 _chua chon list_dd[i] = stt( voi stt = 1->end) *///////////////////////////////////////////////////////////////////////////
HÀM 2:
Mã:
int nhanhCan( int tgt_cha, int w_cha, int stt, int *list_dd/) { //bat buoc phai sap xep du lieu truoc khi sd nhanhCan /**/printf("
tgt_cha=%d w_cha=%d stt=%d", tgt_cha, w_cha, stt); int tgt = 0, w = 0, stt_next = 0; float ct = 0; int list_this[max]; for (int i=0; i<max; ++i) if (list_dd[i] != wasUse) list_this[i] = notUse; else list_this[i] = wasUse; list_this[stt] = wasUse; //? //khai bao xong printf("
i_BB = %d", i_BB); for ( i=0; i<i_BB; ++i) { // tinh toan cac gia tri tgt = tgt_cha + DATA[listBB[i]].gTr; w = w_cha - DATA[listBB[i]].trL; printf("
gTr=%d trL=%d, listBB[i] = %d", DATA[listBB[i]].gTr, DATA[listBB[i]].trL, listBB[i]); printf("
tgt = %d\tw = %d", tgt, w); if ( w < 0 ) {// printf("
w = %d", w); continue; } /*==================================================================*/ for( i=0; i<i_BB; ++i) { if(list_this[i] == notUse) { stt_next = i;/*tim vi tri vat next, dung cho tinh ct*/ printf("
\t\t<found::%d", stt_next); break; } else stt_next = isLa; } /*==================================================================*/ if ( (stt_next == isLa) && ( tgt > TGT)) { // day la nut la co dk OK I TGT = tgt; W = w; printf("
Day la nut la: %s
", DATA[listBB[i]].ten); printf("
\t\t>%d<====>%d<", TGT, W); // list duong di:: dong bo hoa voi listKQ // getch(); return 0; } /*==================================================================*/ else { ct = (float)tgt + (float)w * (float)DATA[stt_next].dGi; printf("
CT = %.2f", ct); if ( ct<TGT) continue; else { printf("
**********
De quy: %s
**********", DATA[stt].ten); nhanhCan( tgt, w, stt_next, list_this); return 0; } } } return 0; }
HÀM 3:
Mã:
//////////////////////////////////////////////////////////////////////////int nhanhCan( int tgt_cha = 0, int w_cha = 0, int stt = 0){ int tgt = 0, w = 0, stt_next = 0, i = 0, ii = 1; float ct = 0; printf("
tgt-cha = %d, w-cha = %d, stt = %d", tgt_cha, w_cha, stt); while( i++< soPhantu) { tgt = w = stt_next = 0; if (listBB[i] == wasUse) continue; tgt = tgt_cha + DATA[listBB[i]].gTr; w = w_cha - DATA[listBB[i]].trL; printf("
tgt = %d\tw = %d", tgt, w); if( w<0) continue; stt_next = listBB[i]; listBB[i] = wasUse; for ( ii=0; ii< soPhantu; ++ii) if (listBB[ii] == wasUse) continue; else break; //da co dc ii int tmp = listBB[ii]; listBB[ii] = wasUse; printf("
ii = %d", ii); if ( (ii == soPhantu) && (tgt > TGT) && (w>=0)) { printf("
**********
Day la nut la %s
**********", DATA[listBB[i]].ten); TGT = tgt; W = w; //dong do listBB voi listKQ for ( int iii=0; iii< soPhantu; ++iii) listKQ[iii] = listBB[iii]; } ct = tgt + w*DATA[listBB[ii]].dGi; printf("
ct = %.2f", ct); if ( ct>TGT) { printf("
Thuc hien de quy. tgt = %d, w = %d, stt_next = %d", tgt, w, stt_next); nhanhCan( tgt, w, stt_next); } listBB[i] = stt_next; listBB[ii] = tmp; printf("
********************************************************"); } getch(); return 0;}//////////////////////////////////////////////////////////////////////////
KHAI BÁO + NHẬP LIỆU, IN:
Mã:
#include <stdio.h>#include <conio.h>#include <string.h>#include <ctype.h>#include <process.h>#define max 50#define notUse -2#define wasUse -1#define isLa -3//////////////////////////////////////////////////////////////////////////struct node{ int trL, gTr; char ten[10]; float dGi;};////////////////////////////////////////////////////////////////////////////tao bang vecto anh xa vao mang DATAstatic int listBB[max], listBD[max], listKQ[max];static int i_BB = 0, i_BD = 0, i_KQ = 0;// giong i_datastatic int soPhantu = 0;static node DATA[max];// chi tham khao den chu ko sua doi gi het// static int i_data = 0;// luu tru vi tri cc trong ds dac datastatic node balo;static int TGT = 0, W = 0; // luu tru gia tri cc tim dcFILE *f;static char tenfile[10] = "dt2.dt";static int list_dd_ROOT [max]; //////////////////////////////////////////////////////////////////////////void In( int);//////////////////////////////////////////////////////////////////////////void reset(){ for(int i=0; i<max; ++i) { listBB[i] = listBD[i] = listKQ[i] = i; list_dd_ROOT[i] = notUse; }}//////////////////////////////////////////////////////////////////////////void Bubble( int kieu)// 0: bubble:listBD !0:bubble:listKQ{ int i, j; int tmp, get1, get2; if ( kieu == 0) { for( i=0; i<max; ++i, listBB[i] = listBD[i]); i_BB = i_BD; } else { for( i=0; i<max; ++i, listBB[i] = listKQ[i]); i_BB = i_KQ; } for( i = 1; i <= i_BB; ++i) for( j = i_BB; j > i-1; --j) { get1 = listBB[j]; get2 = listBB[j-1];// printf("
%d:%d\t\t%.2f\t:\t%.2f ", get1, get2, DATA[get1].dGi, DATA[get2].dGi); if( DATA[get1].dGi > DATA[get2].dGi) {// printf("\t<this\t%d::%d", listBB[j], listBB[j-1]); tmp = listBB[j]; listBB[j] = listBB[j-1]; listBB[j-1] = tmp;// printf(" _^o^_ %d::%d", listBB[j], listBB[j-1]); } }} //////////////////////////////////////////////////////////////////////////void docTay(){ printf ("
Nhap vao so do vat toi da: "); scanf("%d", &soPhantu); printf ("Nhap vao trong luong balo: "); scanf("%d", &balo.trL); for (int i=0; i< soPhantu; ++i) { printf ("
*****************************"); printf ("
Do vat thu %d:", i+1); printf ("
\tTEN: "); scanf("%s", &DATA[i].ten); printf ("\tTRONG LUONG: "); scanf("%d", &DATA[i].trL); printf ("\tGIA TRI: "); scanf("%d", &DATA[i].gTr); if (DATA[i].trL ==0) DATA[i].dGi = 1; else DATA[i].dGi = (float)(DATA[i].gTr) / (float)(DATA[i].trL); } i_BD = soPhantu; luuFile();} //////////////////////////////////////////////////////////////////////////void In( int kieu = 0)//0:listBD 1:listBB, 2:listKQ{ int *list_tmp; int i_list; if ( kieu == 0) { list_tmp = listBD; i_list = i_BD; printf("
\t\t****************************************"); printf("
\t\t* SO LIEU BAN DAU *"); printf("
\t\t****************************************"); } else if( kieu == 1) { list_tmp = listBB; i_list = i_BB; printf("
\t ****************************************************"); printf("
\t * SO LIEU SAU KHI DUNG HAM SAP XEP (BUBBLE) *"); printf("
\t ****************************************************"); } else { list_tmp = listKQ; i_list = i_KQ; printf("
\t\t****************************************"); printf("
\t\t* KET QUA *"); printf("
\t\t****************************************"); printf("
Tong trong luong con du: %d", W); printf("
Trong luong tim duoc: %d", balo.trL - W); printf("
Tong gia tri lay dc: %d", TGT); printf("
Bang:"); } int get; printf("
-------------------------------------------------------------------------"); printf("
| STT\t|\tTEN\t|\tTRL\t|\tGTR\t|\tDGI\t|"); printf("
-------------------------------------------------------------------------"); for (int i=0; i<i_list; ++i) { if( list_tmp[i] == wasUse) continue; get = list_tmp[i]; //printf("%d:%d", get, listBD[i]); printf("
| %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, DATA[get].dGi); } printf("
-------------------------------------------------------------------------");}//////////////////////////////////////////////////////////////////////////
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À:
Mã:
=>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À:
Mã:
+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
View more random threads:
Bất chấp những lầm tưởng phổ quát, hồ hết những người có âm đạo đều khó lên đỉnh khi bị kích thích âm đạo. Tuy nhiên, điều đó không có tức thị nó không thể vui được! Việc xâm nhập vào âm đạo bằng...
Quý bà giải tỏa bằng việc kích...