Trình giải bài toán ba lô 0/1

Bài toán ba lô 0/1 là gì?

Bài toán ba lô 0/1 yêu cầu chọn một tập hợp các món đồ, mỗi món chỉ được chọn một lần, sao cho tổng trọng lượng không vượt quá sức chứa của ba lô và tổng giá trị là lớn nhất. Công cụ này sử dụng thuật toán quy hoạch động để tìm lời giải chính xác.

Cách sử dụng với ví dụ cụ thể

Giả sử bạn có ba món đồ: A (trọng lượng 2, giá trị 6), B (trọng lượng 3, giá trị 10), C (trọng lượng 4, giá trị 12) và sức chứa là 5. Nhập dữ liệu như sau:

A,2,6
B,3,10
C,4,12
5

Kết quả sẽ hiển thị tổng giá trị tối đa là 16 và các món đồ được chọn là A và B.

Đặc điểm và giới hạn

• Mỗi món đồ chỉ được chọn tối đa một lần (không phải bài toán ba lô phân số hay đa trọng lượng).
• Số lượng món đồ từ 1 đến 200.
• Trọng lượng phải là số nguyên dương và không vượt quá sức chứa.
• Giá trị có thể bằng 0, nhưng không âm.
• Nếu có nhiều phương án cùng giá trị tối đa, công cụ chỉ đưa ra một phương án, không liệt kê tất cả.
• Không hỗ trợ tối ưu tiêu chí phụ như tổng trọng lượng nhỏ nhất.

Câu hỏi thường gặp

Tôi có thể nhập bao nhiêu món đồ?

Công cụ chấp nhận từ 1 đến 200 món đồ. Mỗi món phải có tên duy nhất và không trống.

Trọng lượng và giá trị có thể là số thập phân không?

Không. Trọng lượng phải là số nguyên dương, giá trị phải là số nguyên từ 0 đến 1.000.000.000. Sức chứa cũng là số nguyên.

Nếu có nhiều cách chọn cùng giá trị tối đa thì sao?

Công cụ chỉ hiển thị một cách chọn tối ưu bất kỳ. Nó không liệt kê tất cả các phương án hoặc tối ưu thêm tiêu chí khác.