Đây là bài toán thuộc dạng bài cái túi:
Cho thỏi vàng, thỏi thứ có giá trị và trọng lượng . Có một cái túi đựng được tối đa trọng lượng . Hãy tìm cách chọn các thỏi vàng cho vào túi sao cho trổng trọng lượng không vượt quá giới hạn của túi và tổng giá trị lớn nhất.
Thuật toán duyệt quay lui:
Mỗi phương án chọn các thỏi vàng có dạng một vec-tơ trong đó:
- (: không chọn thỏi vàng thứ , : có chọn)
- Ta cần tìm một nghiệm sao cho lớn nhất.
Thủ tục Backtracking:
void BT(int i, int sW, int sV) {
+ Nếu i > n:
Cập nhật phương án tốt nhất
Thoát
//Không chọn thỏi vàng thứ i
BT(i + 1, sW, sV)
//Nếu có thể chọn thỏi vàng thứ i thì thử chọn
if (w[i] + sW <= W)
BT(i + 1, sW + w[i], sV + v[i])
}