Chia quà ?

[unfriendlyboy]

Có N món quà với giá trị V1, V2, .... Vn. Hãy chia làm 2 phần sao cho hiệu giữa 2 gt là bé nhất.

Cái này em chỉ biết làm Tổ hợp, ngoài ra kô còn biết làm gì hết :(

[ldt116]

Tìm thử xem trên báo ISM (www.thnt.com.vn) đi, tui nhớ hình như là có (số cũ) của NXH

[novavn]

Bài toán này là một bài toán đơn giản của thuật toán Heuristic thôi. Thực hiện các bước như sau
- Đầu tiên, sắp xếp các món quà từ nhỏ đến lớn theo giá trị.
- Lần lượt lấy từ món quà đầu tiên ra cho đến khi tồng giá trị của những món quà đã lấy ra >= tổng giá trị của N món quà chia 2. Đến lúc đó, ta được 2 nhóm quà, một nhóm đã được lấy ra (I), một nhóm là những món quà còn lại (II).
- Xong tiếp theo là công việc chọn và thử. Lấy từng món quà trong nhóm I thử đổi với một món ở nhóm II, thử xem hiệu có bé hơn không, nếu có thì lưu lại kết quả, còn không thì đổi lại, cứ như vậy cho đến khi không còn cách đổi nào.
Đây là bài toán Heuristic, một dạng toán cơ bản trong lập trình thuật tóan

[bete]

Bồ có thể coi bài đăng của lugia:

http://www.diendantinhoc.com/showthread.htm?t=22864&highlight=chia+k%E1%BA%B9o

[novavn]

Bài viết này là của lugia dùng thuật toán Qui họach động, một thuật toán khó nuốt đối với dân lập trình thuật tóan. Bài toán đặc trưng của Qui họach động là bài toán về Tên Trộm. Còn thuật giải Heuristic thì đơn giản và dễ hiểu hơn nhiều nhưng độ chính xác của thuật toán sẽ không cao khi N cực lớn.

[unfriendlyboy]

Thứ nhất: thuật giải heuristic là gì ?
Thứ hai: Có thể mở rộng bài toán cho M người, N món quà được kô ?

[novavn]

Thuật toán Heuristic như đã nói ở trên đó, thuật toán này thường dùng phương thử đổi rồi xết kết quả.
Hoàn toàn có thể mở rộng bài toán ra, và bài toán này có thể được giải quyết bằng nhiều thuật toán như qui họach động ở trên. Đơn giản nhất, đơn giản hơn cả Heuristic là thuật toán Vét cạn, nhưng mà số người càng cao thì tốc độ tính càng chậm

[unfriendlyboy]

Vậy có cách nào làm bài N người mà ko dùng vét cạn kô ?
Tối ưu nghen :)