Chúng ta sẽ cùng xét trường hợp tên trộm mang chiếc túi xách có dung lượng ví dụ là 17 và trong phòng đột nhập có các đồ vật thuộc 5 loại khác nhau mà kích thước và giá trị được liệt kê như ở hình dưới:

Khi đó tên trộm có thể mang đi 5 đồ vật loại A với tổng giá trị là 20, hay tên trộm có thể chất đầy túi với một đồ vật là D và một đồ vật là E với tổng giá trị (i) đạt được là cost[i-size[j]] + val[j] (vì đồ vật j thêm vào sẽ làm đầy phần còn lại của túi có dung lượng I). Nếu giá trị mới này vượt quá cost[i] (giá trị lớn nhất túi xách dung lượng i có thể đạt được khi không có đồ vật j) thì chúng ta sẽ cập nhật cost[i] và best[i]. Hình dưới đây sẽ minh hoạ từng bước quá trình tính toán trên ví dụ của chúng ta:

Nội dung thực sự của phương án tối ưu (danh sách các đồ vật cần bỏ vào túi xách) có thể tìm lại được dựa vào các giá trịtrong mảng best. Theo định nghiữa, best[M] cho biết đồ vật cuối cùng phải thêm vào túi xách, vậy đồ vật vừa được bỏ vào túi trước đó là best[M-size[best[M]]], cứ lần ngược như vậy ta sẽ có danh sách các đồ vật trong túi xách với tổng giá trị lớn nhất. Đối với ví dụ của chúng ta ở trên, best[17]= C, sau đó ta có best[10]=C và best[3] = A.

*** Thời gian giải quyết bài toán túi xách bằng phương pháp quy hoạch động tỷ lệ với NM.

Do vậy bài toán túi xách có thể giải quyết dễ dàng khi M không quá lớn, nhưng thời gian thi hành chương trình sẽ trở nên khó chấp nhận khi M lớn. Hơn nữa, có một điểm cốt yếu không thể bỏ qua đó là phương pháp quy hoạch động không thể thực hiện được nếu M và những kích thước hay giá trị của các đồ vật là số thực thay vì số nguyên. Đây không phải là rắc rối nhỏ mà là khó khăn chính của phương pháp này.

Tất nhiên, nếu dung lượng, kích thước và các giá trị của các đồ vật đều là số nguyên, chúng ta có được một nguyên lý cơ bản là quyết định tối ưu, khi đã được chọn thì không cần thay đổi. Một khi đã biết cách tốt nhất để bỏ đồ vào túi xách có kích thước bất kỳ với j đồ vật ban đầu, ta không cần xem xét lại những vấn đề đó nữa, bất kể những đồ vật sẽ chọn tiếp theo là gì. Khi nào nguyên lý tổng quát này còn hoạt động được, thì phương pháp quy hoạch động còn ứng dụng được. Trong trường hợp này, nguyên lý hoạt động được ví với các giá trị nguyên ta có thể chọn được một quyết định chính xác, tối tưu.

Bài toán chiếc túi xách có thể được tổng hợp lại như sau:
Có N loại đồ vật, mỗi loại có số lượng không hạn chế. Đồ vật loại Îi, đặc trưng bởi trọng lượng Wi và giá trị sử dụng Vi, với mọi i{1,..,n}. Cần chọn các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng M, sao cho tổng giá trị sử dụng các vật được chọn là lớn nhất.
Dưới đây là cài đặt của thuật toán:
void Try(int i)
{
int j, t, g;
t = (int)((m-Tl)/w[i]);
for (j = t; j >=0 ; j--)
{
x[i] = j;
Tl = Tl + w[i]*x[i]; //Trong luong thu duoc
S = S + v[i]*x[i]; //Gia tri thu duoc
if(i==n) //Cap nhat toi uu
{
if(S > Gttu)
{
Gan();
Gttu = S;
}
}
Else
{
g = S + v[i+1]*(m-Tl)/w[i+1]; //Danh gia can
if ( g > Gttu)
Try(i+1);
}
Tl = Tl - w[i]*x[i];
S = S - v[i]*x[i];
}
}
//*************
void Init()
{
for (int i = 1; i <= n; i++)
{
Patu[i] = 0;
x[i] = 0;
}
S = 0;
Gttu = 0;
Tl = 0;
}

School@net