Bài toán xếp ba lô

Bách khoa toàn thư mở Wikipedia



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ô