


(
*
)

Phương pháp quy hoạch động là một kĩ thuật được áp dụng để giải các bài toán tìm phương án tối
ưu . Vậy ý tưởng của phương pháp quy hoạch động thật đơn giản : Để tránh việc tính lại mọi thứ
hai lần , ta lưu giữ kết quả đã tìm được vào một mảng làm giả thiết cho việc tìm kiếm những kết quả
cho trường hợp sau . Chúng ta sẽ làm đầy dần giá trị của bảng này . Bởi các kết quả của những
trường hợp trước đã được giải quyết . Kết quả cuối cùng cũng chính là kết quả cần giải .
Quy hoạch động là dùng kĩ thuật đi từ dưới lên . Xuất phát từ trường hợp đơn giản nhất , có thể
tìm ngay ra nghiệm bằng cách kết hợp nghiệm của chúng , ta nhận được nghiệm của bài toán cỡ
lớn hơn . Cứ như thế ta nhận được đủ nghiệm của bài toán cần tìm .Trong quá trình đi “ Từ dưới
lên “ chúng ta sẽ sử dụng một bảng lưu giữ lời giải của các bài toán con đã được giải. Khi giải một
bài toán cần đến nghiệm của những bài toán nhỏ hơn ta chỉ việc tìm kiếm trong bảng . Chính vì vậy
mà thuật toán “ Quy hoạch động “ là rất có hiệu quả .
ABSTRACT
Dynamic programming is the method of solving complex problems for optimal solutions.
The ideas behind Dynamic programming are very simple:
In order to avoid recalculating everything, we store the solutions to the subproblems in a table
which is used as a fundamental theory to solve new problems. We will build up the values of the
table by adding the solved results of the previous problems. Therefore, the solution to a given
optimal problem can be obtained by the combination of optimal solutions to its subproblems. In
another word, Dynamic programming holds the strengths of the “divide and rule” principle to high
esteem.
Dynamic programming applies the Bottom-up approach. On solving the simpler problems, we can
use the solutions to build on and arrive at solutions to bigger problems. Hence, we can formulate a

8 10 : 1 2 4 6
7  

  



      . Nói cách khác
 

 ). 
                  
 
 
          
. Chính
hu.
2.1. 
- 
2.
- .
- Các bài toán c.
2.3. 

- .
- 
phân t k
 

-  í 

G
k
. Thì:
F
k
=F
k-1
+ G
k

Hay là :
F
k
(t(k))=Max{ G
k
(t(k),d(k))+F
k-1
(t(k-1))} (*)
 d(k)
4.3. 
- i. . 

- 
 - 
k

-  con

Thí dụ:
HOA.INP
HOA.OUT
4 6
1 1 6 4 3 10
9 1 4 7 2 7
7 2 6 10 2 3
6 10 7 1 3 9

24
1 3 4 6

Hướng giải: 
Ta tiến hành như sau:
5.: Gọi b[i][j] là giá trị thẫm mĩ khi cắm i bó hoa vào j lọ, ta thấy:
5.1.1. No .
5.1.2. N
5.1.3. T. 


-
-  :
b[i-1][j-1]+ V[i][j].
ào (j-

Doøng i

[i][j -1]
[i][j]

. L[i][j] 
, 
-1][j-1]+V[i][j]>b[i][j-
-1][j-1]+V[i][j] 
-1][j-u : - L[i][j]=L[i-1][j-1] 
b[i-1][j-1]+V[i][j]<=b[i][j-1] -
án [i][j-1]
5.



if(i>j)
return i;
return j; }
/
void taobang(){
for(int i=1;i<=k;i++)
for(int j=i;j<=n-(k-i);j++)
b[i][j] = getmax( b[i][j-1] , (b[i1][j1] )
//
void trabang(){
int i=k;j=n;
kq=b[i][j];
do {
while(b[i][j]==b[i][j-1]) j ;
vt[i]=j; i ;j ;}
while (i>-1);
}
//
void xuat(){
FILE *f=fopen(fo,"wt");
if(kq==-1) fprintf(f,"1");
else {
trabang();
fprintf(f,"%d\n",kq);
for(inti=1;i<=k;i++)
fprintf(f,"%5d",vt[i]);
}


If v>=A[k] then
F
x
[k][v]= Max(F
x
[k-1][v-A[k]]+B[k],F
x
[k-1][v])
Else
F
x
[k][v]= F
x
[k-1][v].

x

v
k
1
2
3
4
5
6
7
8
9
10

9
3
0
0
4
5
6
6
9
10
11
11
11
15
15
4
0
3
4
5
7
8
9
10
12
13
14
15
15
5

16
1(3,4) 2(4,5) 3(5,6) 5(1,1) FILE *f=fopen(fi,"rt"); fscanf(f,"%d%d",&n,&w); for(int i=1;i<=n;i++)
fscanf(f,"%d%d",&a[i],&gt[i]);fclose(f);
}
int getmax(int i,int j){
if(i>j)return i;
return j;
}
void taobang(){
int i,j; for(j=1;j<=w;j++) if(a[1]>j) b[1][j]=0;
else b[1][j]=gt[1];
for(i=2;i<=n;i++)
for(j=1;j<=w;j++) if(j>=a[i])
b[i][j] =getmax(b[i-1][j],(b[i-1][j-a[i]]+gt[i]) );
else b[i][j]=b[i-1][j];
}
void trabang(){
int d=n,c=w,tam; kq=tam=b[d][c];
do{ while(b[d][c]==b[d-1][c]) d ; while(b[d][c]==b[d][c-1]) c ;
vt[d]=1;c-=a[d];
}while(c>0);
}
void xuat(){
FILE *f=fopen(fo,"wt");
trabang();
fprintf(f,"%d",kq);
for(int i=1;i<=n;i++)