    
a 
  
   

Bài toán
Trtin tha
Ba lô
Chin lưc tham n
Cây bao trùm nhnht
Thut toán Prim
Thut toán Kruskal
!   a
Các loing xu 100c, 25c, 10c, 5c, 1c
Vi khon tin cn trli, sao cho s
lưng ng xu là ít nht.
Ví d: trli 189c
189 xu 1c => 189
18 xu 10c, 1 xu 5c, 4 xu 1c => 23
!   a
Slưng ng xu trli là ít nht?
Ý tưng:
Sdng ln lưt các ng xu có mnh giá t
ln nhtn nhnht
Hy vng slưng ng xu là ít nht
Ví d: trli 189c
1xu 100c, 3xu 25c, 1xu 10c, 4xu 1c => 9
9 xu ã ít nht chưa
" #  $ 
Thưng áp dng cho bài toán tiưu
Xác nh ưc li gii tiưu
Da trên li gii tiưu các bài toán con
Có thphc tp hóa vn
Không khthi vi bài toán thc t
Không gian tìm kim rng
Thi gian tìm kim lâu