XEM THÊM Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị Kiểm tra đồ thị liên thông trong bài toán đồ thị lập trình Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++ Tìm dãy con có tổng trọng số lớn nhất trong lập trình C/C++ Tính A^n bằng phương pháp chia để trị Quy hoạch động tìm xâu con chung độ dài lớn nhất
Trong bài viết này chúng ta sẽ cùng làm bài toán là tìm dãy con có tổng trọng số lớn nhất trong mảng.
Cụ thể bài toán có thể phát biểu như sau: Viết chương trình tìm dãy con có tổng trọng số lớn nhất trong mảng, tính tổng trọng số và in ra dãy con đó. Sử dụng 3 phương pháp là duyệt qua tất cả phần tử mảng, quy hoạch động và chia để trị.
Ví dụ: -5 0 -4 1 5 -2 5
Dãy con có tổng trọng số lớn nhất là: 5 -2 5 1 và có tổng trọng số là 9.
Giải bằng phương pháp duyệt qua tất cả phần tử
Đối với bài toán này thì phương pháp này là đơn giản nhất mà hầu hết ai cũng có thể nghĩ ra và làm được, tuy nhiên thuật toán lại không hề tối ưu và chạy rất tốn time nếu mảng từ vài trăm ngìn phần tử.
Ý tưởng là ta sẽ duyệt 3 vòng lặp để lấy hết từng dãy con của mảng và tính tính tổng. Duyệt đến dãy con nào có tổng trọng số lớn hơn thì ta sẽ gắn bằng maxx và lưu dãy con vào một mảng temp, thực hiện lặp cho đến khi hết tất cả dãy con lúc đó maxx chính là tổng trọng số lớn nhất, temp là dãy con đó.
- Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
- Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
- Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
Ta viết chương trình như sau:
#include <iostream>
using namespace std;
int main()
{
int a[]={-5,0,-4,1,5,-2,5}; //mảng a
int n = sizeof(a)/4; //Số phần tử mảng a
int maxsum = 0; //tổng dãy con lớn nhất
int sum = 0; //sum để tính tổng từng dãy con
int vtd = 0, vtc = n-1; //Lưu vị trí đầu và cuối để lát nữa lấy ra dãy con đó(hiểu là mảng temp)
//Vòng lặp i j để lấy từng dãy con có trong mảng có thể sảy ra
//Ví dụ dãy con có thể là từ vt1 tới vt5, vt3 tới vt4, vt2 tới vt4....v.v
for (int i = 0; i < n; i++) {
for(int j=i;j<n;j++)
{
sum=0; //Gắn lại biến tổng dãy con = 0
//Vòng lặp k để tính tổng của dãy con từ phần tử vt i tới vị trí j
for(int k=i;k<=j;k++)
{
sum+=a[k]; //cộng dồn Tính tổng dãy
}
//Nếu maxsum( tổng lớn nhất trước đó tìm được) mà nhỏ hơn sum(tổng dãy con hiện tại)
if(maxsum < sum)
{
maxsum = sum; //Gắn lại tổng dãy con lớn nhất là sum hiện tại
vtd = i; vtc = j; //Gắn lại dãy con
}
}
}
//Hết vòng lặp ta in ra kết quả
cout<<maxsum<<"\n";
for(int i=vtd;i<=vtc;i++) cout<<a[i]<<" ";
return 0;
}
Giải bằng phương pháp quy hoạch động
Đọc thêm: Tìm hiểu thuật toán Quy hoạch động
Code quy hoạch động cho bài toán này thì nhìn rất ngắn gọn. Công thức truy hồi được tìm ra bằng cách.
Ta duyệt từ đầu mảng đi, cứ tới vị trị nào mà có tổng trọng số nhỏ hơn 0 ta bỏ luôn dãy con từ vị trí đó và tính lại sum từ phần tử tiếp theo tại vị trí đó trở đi. Bởi vì nếu đoạn trước đó đã < 0 thì cộng vào trọng số cho đoạn sau sẽ chỉ nhỏ đi chứ không thể tăng lên nên ta cắt luôn từ vị trí đó.
Ta viết code như sau:
#include <bits/stdc++.h>
using namespace std;
int vt;
//Hàm quy hoạch động
int QHD(int a[], int n)
{
int temp=0, maxsum=0; //Biến temp hiểu là biến sum(tổng tạm thời), maxsum là tổng trọng số dãy con lớn nhất tìm được
for(int i=0;i<n;i++)
{
//Nếu temp < 0 thì gắn => đoạn đó có tổng nhỏ hơn 0 nên ta gắn lại temp = 0 để bắt đầu tính tổng từ vị trí tiếp theo
//Ngược lại ta cộng dồn temp+=a[i]
temp+a[i]<0?temp=0:temp+=a[i];
//Nếu temp mà lớn hớn maxsum trước đó tìm được
if(temp > maxsum){
maxsum = temp;vt=i; //Gắn lại maxsum và vị trí kết thúc của dãy con
}
}
return maxsum;
}
int main ()
{
int a[]={-5,0,-4,1,5,-2,5};
int n = sizeof(a)/4;
int sum = QHD(a,n); //Gọi uy hoạch động với dãy a
//In ra tổng trọng số
cout<<sum<<endl;
/*Vì ta chỉ lưu vị trí dãy con kết thúc nên ta sẽ duyệt mảng a từ vị trí đó
ngược lại qua đầu mảng và in ra từng phần tử, trừ dần đi phần tử đến khi nào sum = 0 thì tức là tổng
trọng số ta tính từ đoạn đó trở đi
*/
while(sum>0)
{
cout<<a[vt]<<" ";
sum-=a[vt];vt--;
}
return 0;
}
Giải bằng phương pháp chia để trị
Đọc thêm: Tìm hiểu thuật toán chia để trị trong lập trình, ví dụ áp dụng
Trong bài toán này thì có lẽ sử dụng phương pháp chia để trị là phương pháp khó làm nhất. Ta sẽ chia dần mảng con nhỏ dần cho tới lúc không thể chia nhỏ, sau đó tính toán và hợp nhất lại để tính kết quả cuối cùng của bài toán.
Ta viết code chia để trị như sau:
#include <bits/stdc++.h>
using namespace std;
int vt1, vt2, vt;
int maxleft (int a[], int i, int j)
{
int maxsum = 0;
int sum = 0;
for (int k = j; k >= i; k--){
sum = sum + a[k];
if(sum > maxsum) {
maxsum = sum;
vt1 = k;
}
}
return maxsum;
}
int maxright (int a[], int i, int j){
int maxsum = 0;
int sum = 0;
for (int k = i; k <= j; k++){
sum = sum + a[k];
if(sum > maxsum) {
maxsum = sum;
vt2 = k;
}
}
return maxsum;
}
int maxsub(int a[], int i, int j){
if (i == j) return a[i];
int m = (i + j)/2;
int wL = maxsub (a, i, m);
int wR = maxsub (a, m+1, j);
int wM = maxleft(a, i, m) + maxright(a, m+1, j);
if(wL > wR) vt = vt1;
else vt = vt2;
return max (max(wL, wR), wM);
}
int main ()
{
// int N;
// cin >> N;
// int a[N];
// for(int i = 0; i < N; i++) cin >> a[i];
int a[]={-5,0,-4,1,5,-2,5};
int N = sizeof(a)/4;
int sum = maxsub (a, 0, N-1);
cout << sum << endl;
for(int i = vt; i >= 0; i--) {
if(sum > 0) {
cout << a[i] << " ";
sum -= a[i];
}
}
return 0;
}
Cuối cùng thì mình xin cảm ơn bạn đã đọc bài viết, chúc bạn học tốt! sớm trở thành một Pro Dev.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
