 ý tưởng:

 Để tìm bộ nghiệm tối ưu cho bài toán ta chọn một tiêu chí quan tâm

Nhất và thiết kế giải thuật sao cho càng đạt được càng nhiều tiêu chí

Càng tốt.

Ưu điểm: thời gian thực hiện nhanh, giải thuật được thiết kế không quá phức

tạp và thường đạt được nghiệm chấp nhận đối với các bộ dữ liệu thực tế.

Nhược điểm: chỉ có thể tìm được nghiệm xấp xỉ tối ưu thay vì nghiệm tối ưu.

- thủ tục :

Begin

S:= Æ ;

While (A <> Æ) or (<chưa đạt được nghiệm>) Do

begin

x:= Select(A);

A:= A - {x};

if <S U{x} chấp nhận được> then S:= S U{x};

end;

End;

- độ phức tạp thuật toán

+ Giải thuật :

1-tư tưởng :

Ban đầu ta có một tập A các phần tử được chọn của bài to

Ta xây dựng một tập S dần từng bước bắt đàu từ tập rỗng.

Tại mỗi bước ta sẽ chọn một phần tử "tốt nhất" trong các phần tử của A để đưa vào S. Phần tử được chọn sẽ bị loại khỏi S.

Nếu khi thêm phần tử đựơc chọn vào tập S mà S vẫn thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào các phần tử được chọn.

2-thủ tục tổng quát :

Void Thamlam(long A, long s)

{ //A là tập các ứng cử viên, S là nghiệm

S = Ø;

while (A != Ø)

{<chon x tu A>

x = select(A);

A = A - {X};

if (S U {X}) < chấp nhận được>

S = S + {X};

}

}