Bài toán xếp ba lô
Bách khoa toàn thư mở Wikipedia
![]() |
Đang bàn cãi về giá trị của bài này. Có thể trang này không xứng đáng có một bài viết về nó ở Wikipedia. Xin xem trang thảo luận. |
dùng cho câu số lượng đồ vật không hạn chế a[i] : thể tích của đồ vật thứ i c[i] : giá trị của 1 đồ vật thứ i g[i,j] = là giá trị lớn nhất khi đặt i đồ vật từ đồ vật 1,2,…,i vào balo có thể tích j x[i,j] = là số lượng đồ vật thứ i cần thiết khi đặt i đồ vật từ đồ vật 1,2,…,i vào balo có thể tích j đạt giá trị lớn nhất. Bước 1: Khởi trị, x[1,j] = j div a[1] g[1,j] = x[1,j]*c[1] Bước 2: Giải Với mọi k Î [2..n] do
Với mọi v Î [1..m] do Với mọi u Î [0..v] do xk = (v – u) div a[k] max = g[k-1,u]+c[k]*xk if max>g[k,v] then begin g[k,v] = max x[k,v] = xk end Cuối mọi Cuối mọi
Cuối mọi
Bước 3: Tìm lời giải g[n,m]: là giá trị lớn nhất khi đặt n đồ vật vào ba lô có thể tích m Để tìm cách chọn đồ vật ta thực hiện như sau: K = n V = m Lặp
Need[k] = x[k,v] V = v – need[k]*a[k] Dec(k)
Cho đến khi k=0 Kết quả Need[i] sẽ là số lượng đồ vật thứ i cần bỏ vào ba lô