Bài toán cái túi — 0/1 Knapsack, Unbounded và nén bộ nhớ

TL;DR: Bài toán cái túi (knapsack) hỏi: chọn một tập món đồ (item) sao cho tổng weight không vượt W và tổng value lớn nhất. Với 0/1 knapsack (mỗi món dùng tối đa 1 lần), DP 2D dp[i][w] là giá trị tốt nhất khi xét i món đầu với sức chứa w. Transition: chọn hoặc không chọn món thứ i. Nén xuống 1D bằng cách duyệt w từ W xuống 0. Greedy (chọn theo tỉ lệ value/weight) sai với 0/1 knapsack, và một counter-example đơn giản là đủ để bác bỏ.

Một công ty logistics phải chọn đơn hàng nào để xếp vào chuyến xe tải 1.000 kg cuối ngày. Mỗi đơn hàng có trọng lượng và lợi nhuận riêng. Mục tiêu: lời nhiều nhất mà không vượt tải trọng. Đơn hàng không chia nhỏ được, mỗi đơn hoặc lấy hết hoặc bỏ qua. Đó đúng là cấu trúc của 0/1 Knapsack.

Cùng khuôn này gặp ở danh mục đầu tư (chọn dự án với ngân sách cố định), cache (object nào giữ trong RAM) hay scheduling (task nào làm trong giờ làm việc).

1. Hình dung: packer thông minh so với packer tham lam

Cứ hình dung hai nhân viên xếp hàng vào kho:

• Packer tham lam luôn chọn món có tỉ lệ value/weight cao nhất. Nghe có lý, nhưng hay bị kẹt: chọn món đắt và khá nặng xong thì hết chỗ cho hai món nhẹ, rẻ mà cộng lại còn lời hơn.
• Packer DP nghĩ khác: "Nếu còn w kg và tôi đang xét món thứ i, thì lựa chọn tối ưu là gì?" Mỗi quyết định nhỏ được lưu lại để dựng nên quyết định lớn hơn.

2. Phát biểu bài toán và ký hiệu

Cho n món đồ (item), món i có:

• weight[i]: trọng lượng (số nguyên dương)
• value[i]: giá trị (số nguyên dương)

Và sức chứa tối đa W. Tìm tập con các món có tổng weight không vượt W và tổng value lớn nhất.

0/1 knapsack: mỗi món dùng tối đa 1 lần (lấy hoặc bỏ). Unbounded knapsack: mỗi món dùng được nhiều lần tuỳ ý.