Thuyết minh Giải pháp Vận dụng phương pháp qui hoạch động vào giải các bài toán trong ôn thi học sinh giỏi môn Tin học

t t2=a[i].v;
int t3=a[i].c; int t=1;
for(int j=1;j<=t3;j++)
{
V[++len]=t*t2; W[len]=t*t1;
}
}
for(int i=1;i<=len;++i)
{
for(int j=m;j>=W[i];j--)
{
f[j]=max(f[j],f[j-W[i]]+V[i]);
}
}
cout << f[m];
}
Bài toán Chia kẹo
Có N gói kẹo đánh số từ 1 đến N, gói thứ i có số kẹo là Ai, i = 1. . N. N gói kẹo được chia làm 2 phần khác nhau.
Yêu cầu: tìm cách chia sao cho độ chênh lệch tổng số kẹo giữa hai phần là ít nhất.
Input: đọc từ file văn bản KEO.INP gồm 2 dòng:
+ Dòng 1: ghi số nguyên dương N, (N ≤ 200)
+ Dòng 2: ghi lần lượt A1, A2,  , AN. Ai ≤ 1000 các số trên cùng một dòng cách nhau ít nhất một dấu cách
Output: ghi ra file văn bản KEO.OUT gồm 3 dòng:
+ Dòng 1: ghi D là độ chênh lệch ít nhất
+ Dòng 2: ghi số hiệu các gói thuộc phần thứ nhất
+ Dòng 3: ghi số hiệu các gói thuộc phần thứ hai
Example:
KEO.INP
KEO.OUT
4
3 4 7 12
2
3 4 7
12
Giải thuật:
Ta sử dụng mảng f[] để lưu các tổng nhỏ hơn hoặc bằng s/2 bằng cách cộng một số phần tử .
Đồng thời lưu vết các giá trị của a được chọn để tổng chúng bằng S vào một mảng vết
Trường hợp cơ sở :
f[0]=1 (do chúng ta luôn có dãy có tổng bằng 0).
Sau khi đã tính được mảng f[], vì tổng càng gần S/2 thì độ chêch lệch càng nhỏ nên chúng ta duyệt từ S/2 đến 1 để tìm giá trị i lớn nhất sao cho f[i] là true(có thể tạo ra được tổng i).
Khi tìm được i: đáp án sẽ là S-2*i, vì chúng ta chia dãy thành hai phần có tổng lần lượt là i và S-i.
Cuối cùng ta đánh dấu các vết đó vào một mảng b[maxn] để lưu số hiệu ở phần thứ hai được chọn.
Nếu b[i] = 1 thì số hiệu đó thuộc phần thứ 2 Ngược lại thì số hiệu đó thuộc phần thứ 1
Ở phần thứ nhất ta duyệt các phần tử từ 1 tới n: nếu b[i]!=1 thì sẽ in ra i là các chỉ số của phần thứ nhất
Ở phần thứ hai ta duyệt các phần tử từ 1 tới n: nếu b[i]=0 thì sẽ in ra i là các chỉ số ở túi thứ 2.
Code C++
#include using namespace std; #define ll long long const int maxn=205;
int n;
int a[maxn]; ll s=0;
ll f[maxn]; ll b[maxn];
int vet[maxn]; int main()
{
freopen("KEO.INP","r",stdin);
freopen("KEO.OUT","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0);
cout.tie(0); cin >> n ;
for(int i=1;i> a[i] , s+=a[i]; ll t=s/2;
f[0]=1;
for(int i=1;i<=n;++i)
{
for(int j=t;j>=a[i];--j)
{
if(f[j-a[i]]==1)
{
f[j]=1;
if(vet[j]==0) vet[j]=i;
}
}
}
while(f[t]==0)
{
t--;
}
cout 0)
{
b[vet[t]]=1;
t-=a[vet[t]];
}
for(int i=1;i<=n;++i)
{
if(b[i]!=1) cout << a[i] << " ";
}
cout << '\n';
for(int i=1;i<=n;++i)
{
if(b[i]==1) cout << a[i] << " ";
}
}
Bài toán Bố trí phòng họp
Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần được bắt đầu tại thời điểm si và kết thúc tại thời điểm fi. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp sao cho khoảng thời gian làm việc của hai cuộc họp được nhận phục vụ chỉ có thể giao nhau tại đầu mút.
Input: đọc từ file văn bản ACTIVITY.INP gồm:
Dòng dầu tiên chứa số nguyên dương n (n <= 1000000)
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương si, fi (si, fi <= 32000), i=1, 2, , n. Mỗi số trên cùng dòng cách nhau 1 dấu cách
Output: ghi ra file văn bản ACTIVITY.OUT gồm:
Dòng đầu tiên ghi số k là số lượng cuộc họp được chấp nhận phục vụ;
Mỗi dòng trong K dòng tiếp theo ghi chỉ số của một trong k cuộc họp được chấp nhận
Ví dụ :
ACTIVITY.INP
ACTIVITY.OUT
5
1 3
2 4
1 6
3 5
7 9
3
1
4
5
Giải thuật:
Ban đầu ta cần tạo một struct bao gồm: s : thời điểm bắt đầu cuộc họp
f : thời điểm kết thúc cuộc họp p : chỉ số của cuộc họp
Sắp xếp các cuộc họp tăng dần theo thời điểm bắt đầu a[i].s, cuộc họp i sẽ bố trí được sau cuộc họp j khi và chỉ khi j<i và a[j].f≤a[i].s
Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên, bài toán trở thành bài toán tìm dãy tăng dài nhất.
Gọi f[i] là số lượng cuộc họp được chấp nhận phục vụ khi xét đến cuộc họp thứ i, khi đó f[n] là số lượng cuộc họp được chấp nhận phục vụ sau khi xét n cuộc họp, do đó f[n] là kết quả của bài toán
Do bài toán yêu cầu cần in ra chỉ số của các cuộc họp được chấp nhận nên ta cần có một mảng để lưu vết nên cần khởi tạo một mảng vet[maxn]
Nếu a[j].f≤a[i].s : xét f[i] và f[j] + 1 : Nếu f[i] < f[j]+1 thì :
Gắn f[i]=f[j]+1 ; // tức là có thêm 1 cuộc họp được chấp nhận thỏa mãn đề bài đồng thời ta lưu vết cuộc họp đó vào : vet[i]=j
Tiếp theo ta cần đánh dấu các cuộc họp đc chấp nhận đó vào một mảng để in ra màn hình bằng cách duyệt các vết đã lưu sau đó cho vào mảng đánh dấu để hiểu rằng cuộc họp đó đã chấp chận
int t=1; for(i=1;i<=n;++i)
{
if(f[i]>f[t])
{
t=i;
}
}
while(t>0)
{
b[a[t].p]=1; t=vet[t];
}
Code ++
#include
using namespace std; #define ll long long const int maxn=1e6+7; int n,i;
struct Data{
ll s,f,p;
} a[maxn];
bool cmp(Data &a,Data &b)
{
return a.s < b.s || (a.s==b.s && a.f < b.f);
}
namespace sub1{
ll f[maxn],vet[maxn]; ll b[maxn];
void Main(){
sort(a+1,a+1+n,cmp); for(i=1;i<=n;++i){
f[i]=1;
for(int j=1;j<i;++j){
if(a[j].f <=a[i].s && f[i] < f[j]+1)
{
vet[i]=j; f[i]=f[j]+1;
}
}
}
cout << f[n] << '\n'; int t=1; for(i=1;i<=n;++i)
{
if(f[i]>f[t])
{
t=i;
}
}
while(t>0)
{
b[a[t].p]=1; t=vet[t];
}
for(i=1;i<=n;++i)
{
if(b[i]==1) cout << i << '\n';
}
}
}
int main()
{
freopen("ACTIVITY.INP","r",stdin); freopen("ACTIVITY.OUT","w",stdout); ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0); cin >> n ;
for(i=1;i<=n;++i)
{
a[i].p=i;
cin >> a[i].s >> a[i].f;
}
sub1::Main(); return 0;
}
Một số bài toán khác
Bài 1. Cho thuê máy tính (RENTING.*)
Tại thời điểm 0, ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử dụng của N khách hàng. Các khách hàng được đánh số từ 1 đến N. Khách hàng i cần sử dụng máy từ thời điểm di đến thời điểm ci (di và ci là các số
nguyên và 0 < di < ci < 109), và sẽ trả tiền sử dụng máy là pi (pi nguyên,
0 < pi < 109);
Yêu cầu: Hãy xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận phục vụ bất kì không giao nhau và tổng tiền thu được từ phục vụ là lớn nhất.
Input: đọc từ file văn bản RENTING.INP gồm:
+ Dòng 1: ghi số N (0 < N <1000)
+ Các dòng tiếp theo, dòng thứ i ghi ba số di, ci, pi cách nhau bởi dấu cách i=1,2,..,N.
Output: ghi ra file văn bản RENTING.OUT gồm:
+ Dòng 1: ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận được phục vụ và tổng tiền thu được.
+ Dòng 2: ghi chỉ số của khách hàng được phục vụ.
*Example:
RENTING.INP
RENTING.OUT
3
150 500 150
1 200 100
400 800 80
2 180
2 3
Bài 2. Tam giác bao nhau (TAMGIAC.*)
Cho N tam giác trên mặt phẳng tam giác i bao tam giác j nếu 3 đỉnh của tam giác j đều nằm trong tam giác i (có thể nằm trên cạnh). Hãy tìm tam giác bao nhau có nhiều tam giác nhất.
Input: đọc từ file văn bản TGBAONHAU.INP gồm:
Dòng 1: ghi số nguyên dương N (1 ≤ N ≤ 1000)
N dòng tiếp theo mỗi dòng ghi 6 số đỉnh của một tam giác.
x1, y1, x2, y2, x3, y3 lần lượt là tọa độ 3
Output: ghi ra file văn bản TGBAONHAU.OUT gồm:
Dòng 1 ghi tọa độ tam giác tìm được
Dòng 2: ghi số tam giác nằm trong tam giác tìm được
Example:
TGBAONHAU.INP
TGBAONHAU.OUT
5
0 8 0 -10 10 8

-4 -4 -2 -2 0 -4
2 0 2 -2 4 0
2 2 4 1 3 4
3 4 3 6 0 4
0 8 0 -10 10 8
4
Bài 3. Dãy con đổi chiều, đối dấu dài nhất (DOICHIEU.*)
Cho dãy a1, a2,... an. Hãy tìm dãy con đổi dấu dài nhất của dãy đó. Dãy con con đổi dấu ai1, ai2,... aik phải thoả mãn các điều kiện sau:
+ ai1 ai3 ai2 ... các chỉ số phải cách nhau ít nhất L: i2
- i1 ≥ L,i3 -i2 ≥ L...
+ Chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |ai1 - ai2| ≤ U, |ai2 - ai3| ≤ U... Ví dụ: Cho dãy 10 phần tử: -1, 3, -4, 13, 6, 9, -2, 12, -3, 15 và L=2 và U=3 có
1 dãy con đổi chiều dài nhất là: -1, -4, -2, -3
Input: đọc từ file văn bản DOICHIEU.INP có cấu trúc như sau:
Dòng đầu tiên ghi 3 số nguyên dương n, L, U (n <105; 1<L<n-1; 0 < U <
1000);

Các dòng tiếp theo ghi n số của dãy a (|ai| <= 32000);
Output: ghi ra file văn bản DOICHIEU.OUT có cấu trúc như sau: Dòng đầu là độ dài dãy con đổi chiều dài nhất tìm được;
Chỉ số các phần tử của dãy con tìm được trong dãy ban đầu;
Example:
DOICHIEU.INP
DOICHIEU.OUT
10 2 3
-1 3 -4 13 6 9 -2 12 -3 15
4
1 3 7 9
Bài 4. Xếp các khối đá (TOWERB.*)
Cho N khối đá (N≤5000) Các khối đá đều có dạng hình hộp chữ nhật và được đặc trưng bới 3 kích thước: dài, rộng, cao. Một cách xây dựng tháp là một cách đặt một số các khối đá trong các khối đá đã cho chồng lên nhau theo quy tắc:
Chiều cao mỗi khối đá là kích thước nhỏ nhất trong 3 kích thước.
Các mép của khối đá được đặt song song với nhau sao cho không có phần nào của khối trên nằm chìa ra ngoài khối dưới.
Hãy chỉ ra cách để xây dựng được một cái tháp sao cho chiều cao của cái tháp là cao nhất
đá i.
Input: đọc từ file văn bản TOWERB.INP có cấu trúc như sau: Dòng 1: ghi số nguyên dương N
N dòng sau dòng i ghi 3 số nguyên dương ≤ 255 là 3 kích thước của khối
Output: ghi ra file văn bản TOWERB.OUT gồm:
Dòng 1 ghi chiều cao cao nhất của tháp sau khi xếp các khối đá.
Các dòng sau ghi các khối được chọn theo thứ tự dùng để xây tháp từ
chân lên đỉnh. Mỗi khối đá ghi 4 số T, D, R, C trong đó T là số thứ tự của mỗi khối đá. D, R, C là kích thước dài, rộng và cao của khối đá tương ứng.
Example:
TOWERB.INP
TOWERB.OUT
5
6 4 2
6 7 3
9 2 1
8 6 3
8 5 2
8
4 8 6 3
2 6 7 3
1 6 4 2

Bài 5. Ba lô – Số đồ vật hạn chế (BALOB.*)
Có một ba lô có thể chứa tối đa trọng lượng M và có n đồ vật (n≤100), đồ vật thứ i có trọng lượng Wi và giá trị Vi; M, Wi,Vi là các số nguyên dương. Hãy chọn và xếp các đồ vật vào ba lô để tổng giá trị của ba lô là lớn nhất.
* Input: đọc từ file văn bản BALOB.INP gồm:
+ Dòng 1: ghi 2 số n, M (0<M<=200) cách nhau ít nhất một dấu cách.
+ n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Wi, Vi (0<Wi, Vi
< 256) cách nhau ít nhất một dấu cách
Output: ghi ra file văn bản BALOB.OUT gồm:
+ Dòng 1: ghi giá trị lớn nhất có thể xếp vào Ba lô
+ Dòng 2: ghi chỉ số những vật được xếp vào Ba lô
Example:
BALOB.INP
BALOB.OUT
5 11
3 3
11
5 2 1

4 4
5 4
9 10
4 4

Bài 6. Dãy con có tổng bằng S (TONG_S.*)
Cho dãy a1, a2,.. an. Tìm một dãy con của dãy đó có tổng bằng S.
Input: đọc từ file văn bản TONG_S.INP có dạng :
+ Dòng 1: là 2 số N, S (N<200, S<=4000);
+ Dòng 2: là N số Ai (i=1, 2,.., N; -32000 <= Ai <=32000).
Output: ghi ra file văn bản TONG_S.OUT gồm 1 dòng là các phần tử thuộc dãy con tìm được, nếu không có dãy con nào có tổng bằng S đưa ra -1;
Example:
TONG_S.INP
TONG_S.OUT
8 39
19 5 20 13 16 20 18 2
19 20
Bài 7. Điền dấu (DAUHOI.*)
Cho n số tự nhiên a1, a2,..., an. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu '?': a1?a2?...?an. Cho trước số nguyên S, có cách nào thay các dấu '?' bằng dấu + hay dấu - để được một biểu thức số học cho giá trị là S không?
Input: đọc từ file văn bản DAUHOI.INP có cấu trúc như sau:
+ Dòng 1 ghi 2 số nguyên dương n và S (n <=104, S<=105);
+ Các dòng tiếp theo ghi n giá trị a1, a2, , an
*Output: ghi ra file văn bản DAUHOI.OUT có cấu trúc như sau:
+ Dòng 1: ghi 0 hoặc 1 tương ứng là không có cách thay các dấu hỏi hoặc có tồn tại cách thay dấu hỏi bằng dấu + hay - để giá trị của biểu thức bằng S;
+ Nếu dòng 1 ghi số 1 thì dòng tiếp theo ghi 1 cách thay dấu hỏi bởi phép toán + hoặc - tìm được (chỉ cần ghi các dấu theo thứ tự từ trái sang phải)
Example:
DAUHOI.INP
DAUHOI.OUT
5 20
4 5 6 7 8
1
-+++
Bài 8. Chia nhóm Expression (ACM 10690)
Cho n số nguyên A1, A2,  , AN. Hãy chia chúng thành hai nhóm sao cho tích của tổng hai nhóm là lớn nhất.
Input: đọc từ file văn bản EXPRESSION.INP gồm 2 dòng:
+ Dòng 1: ghi số nguyên dương N, (N ≤ 1000)
+ Dòng 2: ghi lần lượt A1, A2,  , AN. |Ai| ≤ 1000 các số trên cùng một dòng cách nhau ít nhất một dấu cách
Output: ghi ra file văn bản EXPRESSION.OUT gồm 3 dòng:
+ Dòng 1: ghi T là tích của tổng 2 nhóm tìm được
+ Dòng 2: ghi giá trị các số thuộc nhóm thứ nhất
+ Dòng 3: ghi giá trị các số thuộc nhóm thứ hai
Example:
EXPRESSION.INP
EXPRESSION.OUT
5
2 4 8 5 1
100
2 8
4 5 1

Phạm vi áp dụng sáng kiến
Trong sáng kiến này, tôi trình bày cách giải một số bài toán vận dụng phương pháp qui hoạch động, với mỗi bài toán cụ thể sẽ lựa chọn thuật toán phù hợp để giải quyết bài toán. Vì vậy, sáng kiến này có thể áp dụng vào ôn thi học sinh giỏi trong các trường học. Sáng kiến của tôi đã được áp dụng vào ôn thi học sinh giỏi môn Tin học tại trường PT Dân tộc nội trú tỉnh và một số trường THPT trên địa bàn tỉnh Bắc Giang trong năm học 2023- 2024, qua đó giúp các em học sinh ôn luyện vận dụng phương pháp qui hoạch động để giải quyết tối ưu các bài toán.
Lợi ích kinh tế, xã hội của sáng kiến Về lợi ích kinh tế:
Có thể sử dụng làm tài liệu tự học cho học sinh, giảm thời gian công sức giảng dạy trên lớp.
Về lợi ích xã hội:
Qua việc áp dụng sáng kiến vào trong quá trình giảng dạy bồi dưỡng học sinh giỏi trong năm học 2023- 2024, học sinh được rèn luyện kỹ năng lập trình, khơi dậy niềm say mê, yêu thích đối với bộ môn Tin học, giúp các em học sinh có thể trở thành những lập trình viên chuyên nghiệp hơn, biết nhận dạng bài toán, dựa vào cấu trúc dữ liệu của bài toán để lựa chọn thuật toán tối ưu giải quyết bài toán. Đặc biệt, sau khi áp dụng sáng kiến vào ôn luyện bồi dưỡng học sinh giỏi văn hoá cấp tỉnh môn Tin học (năm học 2023- 2024), chất lượng, kết quả học sinh giỏi tăng lên đáng kể so với năm học 2022- 2023 chưa áp dụng sáng kiến.
Sau đây, tôi xin đưa ra kết quả kì thi chọn học sinh giỏi văn hoá cấp tỉnh môn Tin học trước khi áp dụng sáng kiến (năm học 2022- 2023):
Năm học
Họ và tên học sinh
Kết quả
GV bồi dưỡng
2022- 2023
Hoàng Khánh Điệp
Giải KK
Chu Thị Tú Anh
Kết quả kì thi chọn học sinh giỏi văn hoá cấp tỉnh môn Tin học sau khi áp dụng sáng kiến (năm học 2023- 2024):
Năm học
Họ và tên học sinh
Kết quả
GV bồi dưỡng
2023- 2024
Ngô Văn Duy
Giải KK
Chu Thị Tú Anh
2023- 2024
Hà Lê Nga
Giải KK
Chu Thị Tú Anh

Minh chứng
Học sinh Ngô Văn Duy và Hà Lê Nga đạt giải khuyến khích kì thi chọn HSG văn hoá cấp tỉnh môn Tin học năm học 2023- 2024
Để đề tài của tôi được hoàn thiện hơn, việc sử dụng đạt hiệu quả cao hơn, rất mong các thầy cô và các đồng nghiệp đóng góp ý kiến để việc giảng dạy trong nhà trường ngày càng hiệu quả hơn, giúp các em học sinh học tốt hơn.
Cam đoan: Tôi xin cam đoan những điều khai trên đây là đúng sự thật và không sao chép hoặc vi phạm bản quyền.
Tài liệu tham khảo
[1]. Sách giáo khoa tin học 11, Hồ Sỹ Đàm (chủ biên), NXB Giáo Dục –năm 2007
[2]. Sách bài tập tin học 11, Hồ Sỹ Đàm (chủ biên), NXB Giáo Dục – năm
2007
[3]. Sách giáo viên tin học 11, Hồ Sỹ Đàm (chủ biên), NXB Giáo Dục –
năm 2007.
[4]. Tài liệu, đề thi học sinh giỏi tỉnh Bắc Giang các năm. [5]. Một số tài liệu trên mạng Internet.
XÁC NHẬN CỦA LÃNH ĐẠO NHÀ TRƯỜNG
TÁC GIẢ SÁNG KIẾN


Chu Thị Tú Anh