A view of dynamic programming

canvas-army-knapsack-vintage-canvas-backpacks-girls

Let P be a problem. To solve P, we have a set of resources R which contains n elements { R(1), R(2), … R(n) }. Each subset of R (even empty one) can or cannot solve P but in case it can, there’s a cost of the solving. We have to choose a subset so that the solving cost is best (min or max).

We’ll consider the issue in term of dynamic programming.

Continue reading “A view of dynamic programming”

Mọi bài toán duyệt tổ hợp đều có thể giải bằng Quy hoạch động

Đây là một trong những bài toán như thế

Cho ma trận A(MxN) trong đó a[i][j] = 0 hoặc 1 (M, N <= 100). Mỗi bước biến đổi ma trận là biến toàn bộ 1 hàng hoặc 1 cột thành bit 0 hết. Hãy tính số cách biến đổi ít nhất để được ma trận toàn bit 0.

Xét N cột, rõ ràng việc ta cần làm là chọn ra k cột để KHÔNG áp dụng phép biến đổi (k có thể bằng 0). Hiển nhiên đây là duyệt tổ hợp chập con của N.

Continue reading “Mọi bài toán duyệt tổ hợp đều có thể giải bằng Quy hoạch động”