Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: [bài tập giải thuật] Quy Hoạch Động !

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định [bài tập giải thuật] Quy Hoạch Động !

    Thêm 1 bài cũng khá hay và tiêu biểu cho phương pháp QHD.
    Đề thì Olympic 30/4:
    Xe buýt:
    Trên một tuyến xe đường ở thành phố du lịch X có ô tô buýt công cộng phục vụ việc đi lại của du khách. Bến xe buýt có ở trừng km của tuyến đường. Mỗi lần đi qua bến xe đều đỗ lại cho khách lên xuống. Mỗi bến xe xuất phát từ nó, nhưng mỗi xe chỉ chạy không quá b km kể từ bến xuất phát của nó. Hành khách khi đi xe phải trả tiền cho độ dài đoạn đường mà họ ngồi trên xe. Cước phí cần trả để đi đoạn đường độ dài i là Ci (i=1,2...cool.gif. Một du khách xuất phát từ một bến nào đó muốn đi dạo L km trên tuyến đường nói trên. Hỏi ông ta phải lên xuống xe như thế nào để tổng số tiền phải trả là nhỏ nhất ?
    Dữ liệu vào:
    Dòng đầu tiên chứa 2 số nguyên dương b, L (b<=20; L<=10000)
    Dòng thứ 2 chứa b số nguyên dương C1, C2, ... , Cb được ghi cách nhau bởi một dấu trắng.
    Dữ liệu ra:
    Kết quả ghi vào file văn bản ghi một số duy nhất là chi phí nhỏ nhất tìm được.
    Vd:

    Input:
    10 15
    12 21 31 40 49 58 65 79 90 101
    Output:
    142

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Với bài toán này ta để ý một chút sẽ thấy. Chỉ cần tìm số tiền phải trả nhỏ nhất cho 1 km là bao nhiêu, trong các con số tiền cần phải trả cho từng km kia. Như ta đi 1 km đầu thì phải trả 12/1=12 cho 1 km, nếu đi 2 km đầu phải trả 21/2=10,5 cho 1 km. Cứ theo vậy ta chỉ cần tìm con số phải trả cho 1 km nhỏ nhất trong dãy số Ci, đó là ở 7km đi liên tiếp trả 65. Từ đó tính ra tiếp sẽ có kết quả 142 cho 15 km cần đi.
    Đây là code mà mình ghi. Chưa kịp tối ưu, nhưng đã kiểm tra chính xác.
    Code:
    #include<iostream.h>
    #include<conio.h>
    #include<fstream.h>
    float b,l;
    float a[100],f[100];// f[l] là số tiền trả nhỏ nhất sau khi l km
    float j,i,temp; //j là vị trí có số tiền trả cho 1km nhỏ nhất, temp là số tiền phải trả đó
    void docFile(){
    	ifstream f1("C:\\BT.INP",ios::in);
    	f1>>b>>l;
    	for (i=1;i<l;i++) a[i]=0;
    	for (int i=1;i<=b;i++) f1>>a[i];
    	f1.close();
    };
    void khoiTao(){
    	f[1]=a[1];
    	temp=a[1]/1;
    	j=1;
    };
    void xuly(){
    	for (i=1;i<=l;i++){
    		if (a[i]==0) f[i]=f[j]+f[i-j];
    		else {
    			float t=a[i]/i;
    			if (t>temp){
    				if (f[j]+j[i-j]<=a[i]) f[i]=f[j]+f[i-j];
    				else f[i]=a[i];
    				t=f[i]/i;
    				if (t<temp){
    						temp=t;
    						j=i;
    				};
    			}
    			else{
    				f[i]=a[i];
    				temp=t;
    				j=i;
    			};
    		};
    	};
    };
    
    void ghiFile(){
    	ofstream f2("C:\\BT.OUT",ios::out);
    	f2<<f[l];
    	f2.close();
    };
    void main(){
    
    	docFile();
    	khoiTao();
            xuly();
    	ghiFile();
    	getch();
    };
    Nếu đúng, anh cho thêm bài tập nhé.
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 26-10-2007 lúc 03:27 PM.
    Không biết ghi gì luôn ...

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Hì hì, ý tưởng của ht961711 là hoàn toàn chính xác ^^ ! Bạn giải 1 vòng for rất hay !! Mình thấy code của bạn cũng 2 ngày rồi nhưng do ở trong trường với lại vẫn còn weekday nên chưa coi kĩ được, bạn thông cảm nhé ! Cuối tuần mình sẽ coi kĩ lại nha. Rất vui được thảo luận cùng bạn !

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Hì hì, ý tưởng của ht961711 là hoàn toàn chính xác ^^ ! Bạn giải 1 vòng for rất hay !! Mình thấy code của bạn cũng 2 ngày rồi nhưng do ở trong trường với lại vẫn còn weekday nên chưa coi kĩ được, bạn thông cảm nhé ! Cuối tuần mình sẽ coi kĩ lại nha. Rất vui được thảo luận cùng bạn !
    Hì hì !!! vui quá. Mong được học hỏi thêm ở các thành viên nhiều, chứ mình thì còn yếu lắm. Tiếp tục bài khác nha. Đang hăng hái mà
    Không biết ghi gì luôn ...

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Có phải bạn dùng Borland C++ không nhỉ ! do mình complie bằng TC++ và Visual đều có bug nhiều lắm ^^ ! Nhưng mình đã coi lại ! Bài của bạn là chính xác, có điều không hiểu sao mình sữa lại theo TC++ thì lại ra 144.
    temp=a[1]/1;
    chỗ này thì chắc có lẽ không cần chia 1 ^^ đâu phải không ?
    Với lại 2 mãng a[] và f[] bạn dùng thì mình nghĩ chỉ cần khai báo kiểu int là đủ ! cái giá cước cho 1 Km là riêng biệt mình phải không ?
    Bây h nếu đề bài yêu cầu in ra vị trí xuống xe và lên xe, bạn thử test xem sao nhé !^^
    Đã được chỉnh sửa lần cuối bởi rox_rook : 26-10-2007 lúc 01:17 PM.

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mặc định [bài tập giải thuật] Quy Hoạch Động !

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Có phải bạn dùng Borland C++ không nhỉ ! do mình complie bằng TC++ và Visual đều có bug nhiều lắm ^^ ! Nhưng mình đã coi lại ! Bài của bạn là chính xác, có điều không hiểu sao mình sữa lại theo TC++ thì lại ra 144.
    chỗ này thì chắc có lẽ không cần chia 1 ^^ đâu phải không ?
    Với lại 2 mãng a[] và f[] bạn dùng thì mình nghĩ chỉ cần khai báo kiểu int là đủ ! cái giá cước cho 1 Km là riêng biệt mình phải không ?
    Bây h nếu đề bài yêu cầu in ra vị trí xuống xe và lên xe, bạn thử test xem sao nhé !^^
    Mình dùng Borland C.
    àh, không phải chia 1.
    Nếu mảng a[],f[] khai báo kiểu int, thì khi chia cho một số sẽ bị ép kiểu thành int. Ví dụ: 65/7 = 9 và 79/8=9 nếu khai báo int. Nên ta không xác định được chính xác số tiền phải trả cho 1 km.
    Mình sẽ text lại để in vị trí xuống xe và lên xe sau nha, có việc bận rùi.
    Không biết ghi gì luôn ...

  7. #7
    Ngày gia nhập
    10 2007
    Bài viết
    2

    Giải thuật này sai rồi bạn à. Theo như giải thuật của bạn thì người đó sẽ đi 2 chặng 7km và 1 chặng 1km. Nhưng nếu giá trị C1 được thay bằng 20 thì kết quả thu được sẽ không phải là giá trị tối ưu.

  8. #8
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Trích dẫn Nguyên bản được gửi bởi iam_valkyrie Xem bài viết
    Giải thuật này sai rồi bạn à. Theo như giải thuật của bạn thì người đó sẽ đi 2 chặng 7km và 1 chặng 1km. Nhưng nếu giá trị C1 được thay bằng 20 thì kết quả thu được sẽ không phải là giá trị tối ưu.
    Nếu c1=20 thì kết quả tạm thời tại c8=79 nhỏ hơn kết quả ta tính được là 85. Bạn đúng ở điểm này, vậy ta chỉ cần thêm một đoạn lệnh kiểm tra số tìm được mới cho Ci có nhỏ hơn Ci ban đầu hay không là ok rồi.
    Mình đã sửa lại rồi.
    Cảm ơn bạn !!!
    Không biết ghi gì luôn ...

  9. #9
    Ngày gia nhập
    10 2007
    Bài viết
    2

    Mình thấy như vậy cũng không được bạn à. Theo giải thuật này, người đó sẽ đi 1 chặng 8km và 1 chặng 7km, với tổng chi phí là 79 + 65 = 144. Bây giờ giả sử C8 sẽ là 84. Khi đó tổng chi phí sẽ là 84 + 65 = 149. Đây vẫn chưa phải là kết quả tối ưu vì người đó có thể đi theo 2 tuyến là 6km và 9km với tổng chi phí là 90 + 58 = 148.
    Mình nghĩ giải thuật của bạn sẽ không cho kết quả tối ưu. Vì bộ đường đi của bạn bao giờ cũng sẽ gồm n đoạn p-km ( với p thỏa a[p]/p = min(a[i]/i) ) và một đoạn dư q-km ( 0 <= q <= b ). Nhưng nếu chi phí đi đoạn q-km đủ lớn, (thậm chí đến vô cùng) so với các đoạn còn lại thì luôn tồn tại một bộ đường đi khác có chi phí thấp hơn bộ đường đi này.

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Và có lẽ 1 tuần rồi nên mình cũng nêu cách giải lên luôn, giải thuật rất đơn giản như sau :
    cơ sở QHD là :
    W[1] = C[1]; /* neu chi có 1 tra.m xe thì = chính C[1]--> co so QHD*/
    W[i] = min (W[i-j]) + C[j] ;
    Lời giải bằng C++ :
    C++ Code:
    1.  
    2. #include <iostream>
    3. #include <iomanip>
    4.  
    5. using namespace std;
    6.  
    7. const maxL = 10000;
    8. const maxB = 100;
    9.  
    10. int C[maxB];  /*Mãng chi phí*/
    11. int W[maxL];  /*Mãng xu lý*/
    12. int KQ[maxL]; /*Mãng KQ*/
    13.  
    14. int B; /*Só tram xe*/
    15. int L; /*Doan duong càn di*/
    16. using namespace std;
    17. void Input()
    18. {
    19.         cout << "Xe chay ko qua'B KM: ";
    20.         cin >> B;
    21.         cout << "Ong ta ca`n di L KM : ";
    22.         cin >> L;
    23.        
    24.         /*C[i] là só tie`n ung voi di i KM phai tra*/
    25.         for ( int i = 1; i <= B; i++ )
    26.         {
    27.                 cin >> C[i];
    28.         }
    29. }
    30.  
    31. void QHD()
    32. {
    33.         int _pos; /*Vi trí dang xét*/
    34.         int min;
    35.        
    36.         W[1] = C[1]; /* neu chi có 1 tra.m xe thì = chính C[1]--> co so QHD*/
    37.         KQ[1] = 1;
    38.        
    39.         /*Xet tu`ng KM từ 2-> L*/
    40.         for ( int i = 2; i <= L; i++ )
    41.         {
    42.                 _pos = i;
    43.                 if ( i > B ) _pos = B; /*Ko the di quá B KM*/
    44.                
    45.                 min = maxL;
    46.                 /*Xét tù doan dàu -> _pos de bao dam dó là kq toi uu*/
    47.                 for ( int j = 1; j <= _pos; j++ )
    48.                 {
    49.                         if ( min < W[i-j] + C[j] )
    50.                         {
    51.                               min = W[i-j] + C[j]; /* Tính kq tói uu*/
    52.                               KQ[i] = j; /*Luu vet tram lên xuong xe*/
    53.                         }
    54.                         W[i] = min; /*Luu KQ*/
    55.                 }
    56.         }
    57. }
    58.  
    59. void Output()
    60. {
    61.         cout << "--->" << W[L];
    62.         cout << endl;
    63.        
    64.         int i = L;
    65.         do
    66.         {
    67.                 cout << KQ[i] << setw(3);
    68.                 i = i - KQ[i];
    69.         }while ( i > 0 );
    70. }
    71.  
    72. int main()
    73. {
    74.         Input();
    75.         QHD();
    76.         Output();
    77.  
    78.         return 0;
    79. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 04-03-2008 lúc 02:21 AM.

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

  1. Giải bài toán cái ba-lô bằng kỹ thuật quy hoạch động
    Gửi bởi wild_horse trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 06-06-2015, 05:05 PM
  2. Bài tập C++ Các bác giúp em giải thích thuật toán Quy hoạch động trong bài toán nạy với ạ!
    Gửi bởi NamH trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 16-03-2012, 03:07 AM
  3. Chương trình chấm thi cho các kì thi giải thuật là chương trình gì? Hoạt động thế nào?
    Gửi bởi coolkg1412 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 11-10-2011, 10:17 PM
  4. giải thuật quy hoạch tuyến tính với lập trình C
    Gửi bởi huynhvanchuyen trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 10-12-2010, 03:52 PM
  5. Giải thuật song song cho bài toán quy hoạch động và quay lui
    Gửi bởi chuong01 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 25-06-2010, 09:20 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