Bài toán cái túi – ứng dụng WPF đầu tay

Ứng dụng WPF đầu tay

BÀI TOÁN CÁI TÚI

Phiên bản: 1.0.0.0

1. Giới thiệu

Phát triển và minh họa cho bài toán kinh điển: Bài toán cái túi (bài toán xếp ba lô).

Nội dung bài toán:

Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.

Dạng bài toán quyết định của bài toán xếp ba lô là câu hỏi "có thể đạt được một giá trị ít nhất bằng V mà không vượt ngưỡng chi phí C hay không?"

Chi tiết thuật giải về bài toán này : http://diendan.tinhocmo.net/showthread.php?tid=1348

Trong ứng dụng này, người sử dụng sẽ đóng vai tên trộm đó.

2. Hướng dẫn sử dụng:

Giao diện

Bắt đầu: ta chọn Ứng dụng à Tạo mới, ta có giao diện như sau:

Trước khi bắt đầu , ta được phép chọn các chế độ chơi:

– Thời gian giới hạn: Không giới hạn hoặc Có giới hạn kèm theo số giây giới hạn.

– Cơ sở dữ liệu: ta muốn bài toán với các thông số giá trị, khối lượng đồ vật lấy từ tập tin của ta hoặc cũng có thể để chương trình tự sinh các dãy số ngẫu nhiên với số đồ vật và tổng khối lượng ta nhập vào.

Sau khi chọn chế độ chơi xong, ta click vào Bắt đầu, ta có giao diện

– Lúc này listBox bên trái đã có các món đồ có trong cửa hàng. Mỗi món đồ có số thứ tự , khối lượng và giá trị kèm theo.

– Chính giữa giao diện là thời gian chạy. (nếu chọn không giới hạn thì nó vẫn chạy nhưng không có tự động ngắt) .

– ListBox bên phải chính là danh sách các đồ trong túi. Lúc này chưa có món nào.

– Ta sẽ dùng các nút Lấy hoặc Trả để đưa các món đồ qua lại.

– Trên cùng giao diện hiển thị 2 chỉ số .bên trái là khối lượng còn lại của túi, bên phải là tổng giá trị của các món đồ trong túi.

– Khi ta hoàn tất thì ta nhấn hoàn thành để xác nhận kết quả.

– Các chức năng khác:

    Ø Ứng dụng/Chơi lại: chơi lại với cơ sở dữ liệu trước đó

    Ø Ứng dụng/Đáp án: đáp án đối với cơ sở dữ liệu hiện tại, mình dùng quy hoạch động để lập trình.

    Ø Ứng dụng/Lưu dữ liệu: sẽ cho phép ta lưu cơ sở dữ liệu vào file để có thể mở lại

3. Download ứng dụng tại:

http://www.mediafire.com/?jh884m4t1abj4k3

Video hướng dẫn

Bài toán cái túi – Part 1 – Lập trình giao diện đơn giản Wpf