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

[rox_rook]

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

[Forlorn_hope]

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.

#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é.

[rox_rook]

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 !

[Forlorn_hope]

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à

[rox_rook]

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é !^^

[Forlorn_hope]

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.

[iam_valkyrie]

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.

[Forlorn_hope]

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 !!!

[iam_valkyrie]

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.

[rox_rook]

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++ :

 #include <iostream>#include <iomanip> using namespace std; const maxL = 10000;const maxB = 100; int C[maxB];  /*Mãng chi phí*/int W[maxL];  /*Mãng xu lý*/ int KQ[maxL]; /*Mãng KQ*/ int B; /*Só tram xe*/int L; /*Doan duong càn di*/using namespace std;void Input(){        cout << "Xe chay ko qua'B KM: ";        cin >> B;        cout << "Ong ta ca`n di L KM : ";        cin >> L;                /*C[i] là só tie`n ung voi di i KM phai tra*/        for ( int i = 1; i <= B; i++ )        {                cin >> C[i];        }} void QHD(){        int _pos; /*Vi trí dang xét*/        int min;                W[1] = C[1]; /* neu chi có 1 tra.m xe thì = chính C[1]--> co so QHD*/        KQ[1] = 1;                /*Xet tu`ng KM từ 2-> L*/        for ( int i = 2; i <= L; i++ )        {                _pos = i;                if ( i > B ) _pos = B; /*Ko the di quá B KM*/                                min = maxL;                /*Xét tù doan dàu -> _pos de bao dam dó là kq toi uu*/                for ( int j = 1; j <= _pos; j++ )                {                        if ( min < W[i-j] + C[j] )                        {                              min = W[i-j] + C[j]; /* Tính kq tói uu*/                              KQ[i] = j; /*Luu vet tram lên xuong xe*/                        }                        W[i] = min; /*Luu KQ*/                }        }} void Output(){        cout << "--->" << W[L];        cout << endl;                int i = L;        do         {                cout << KQ[i] << setw(3);                i = i - KQ[i];        }while ( i > 0 );} int main(){        Input();        QHD();        Output();         return 0;}