Bàn về một bài toán hay trong Pascal

Bàn về một bài toán hay

Nguyễn Hiển

Các bạn thân mến! Việc nghiên cứu thuật toán và rút ra kinh nghiệm từ các bài toán hay

luôn là một công việc thích thú với các bạn đam mê lập trình. Trong bài viết này, tôi muốn

giới thiệu với các bạn các cách giải quyết khác nhau cho một bài toán tưởng như đơn giản.

A - BÀI TOĂN

Hôm nay, bạn có nhiệm vụ tân trang lại ô tô của mình. Tất nhiên, có quá nhiều việc phải

làm, vì vậy, bạn muốn thuê các xưởng để sửa chữa làm các công việc đó. Không may, các

xưởng đó lại rất chuyên môn hoá, cho nên bạn phải thuê các xưởng khác nhau cho các

công việc khác nhau. Hơn nữa, họ có xu hướng đòi nhiều tiền hơn với các xe ở tình trạng

tốt hơn. Chẳng hạn, một người thợ sơn có thể đòi tiền nhiều hơn khi sửa 1 ô tô mà toàn bộ

nội thất đã làm bằng da, anh ta sẽ không đòi nhiều tiền cho xe chưa bọc da. Do đó, tiền trả

thêm phụ thuộc vào công việc nào được làm và các công việc làm trước đó. Tất nhiên, bạn

luôn muốn tiết kiệm tiền cho mình bằng một thứ tự tốt nhất cho các công việc.

Các công việc được đánh số từ 1 tới n. Cho giá gốc p của mỗi công việc và tiền trả thêm s

(tính theo đơn vị đồng) đối với một cặp công việc (i,j) là si,j (với i ≠ j), nghĩa là bạn phải trả

thêm si,j đồng cho công việc i nếu và chỉ nếu công việc j được làm xong trước đó. Bạn cần

tính tổng giá tiền nhỏ nhất để hoàn thành các công việc này.Dữ liệu vào: file

INP.DATDòng đầu tiên của file vào chứa số nguyên n (1 ≤ n ≤ 14). Tiếp theo có n dòng,

mỗi dòng chứa đúng n số nguyên: số nguyên thứ i trên dòng này là giá gốc của công việc

thứ i và số nguyên thứ j trên dòng này (i ≠ j) là số tiền si,j phải trả thêm cho công việc i nếu

công việc j được làm trước đó. Các giá tiền là các số nguyên không âm, không vượt quá

100000.

Dữ liệu ra: file OUT.DAT

Ghi ra file 1 số nguyên duy nhất là tổng số tiền nhỏ nhất để hoàn thành các công việc.Ví

dụ:

B - CĂCH GIẢI QUYẾT

Đây là bài toán có nhiều cách giải, với mỗi cách tiếp cận và suy nghĩ về bài toán, chúng ta

có các cách giải quyết khác nhau:

I. CĂCH GIẢI QUYẾT THỨ NHẤT: Duyệt

Dễ thấy, yêu cầu chính của bài toán là sắp xếp n công việc cho trước theo 1 thứ tự xác định