Về một phân hoạch tập các số tự nhiên thành hai tập hợp có tổng các phần tử bằng nhau

Bài viết này chỉ ra rằng chỉ cần thỏa mãn một số điều kiện biểu diễn đơn giản, có thể xây dựng một cầu trung chuyển giữa thuật toán xếp ba lô và thuật toán ăn tham. Nhờ đó, một số các kết quả về phân hoạch tập số nguyên dương thành hai tập hợp có số lượng các phần tử bằng nhau được chứng minh. | VỀ MỘT PHÂN HOẠCH TẬP CÁC SỐ TỰ NHIÊN THÀNH HAI TẬP HỢP CÓ TỔNG CÁC PHẦN TỬ BẰNG NHAU Nguyễn Văn Lợi - Nguyễn Hải Đăng - Nguyễn Thành Khang Đại học Tổng hợp Budapest Hungary LỜI GIỚI THIỆU Bài viết này chỉ ra rằng chỉ cần thỏa mãn một số điều kiện biểu diễn đơn giản chúng ta có thể xây dựng một cầu trung chuyển giữa thuật toán xếp ba lô và thuật toán ăn tham. Nhờ đó một số các kết quả về phân hoạch tập số nguyên dương thành hai tập hợp có số lượng các phần tử bằng nhau được chứng minh. 1. Mở đầu Từ những năm 1990 những nghiên cứu các bài toán tối ưu của toán học rời rạc bắt đầu phát triển. Việc phân bổ các tập hợp con theo những điều kiện cho trước rất nhiều lần thuật toán xếp ba lô và thuật toán tham ăn được sử dụng. Bài toán xếp ba lô được phát biểu như sau tìm cách chọn các đồ vật để xếp vào hai chiếc ba lô làm sao mỗi ba lô chứa được nhiều đồ nhất có thể. Thuật toán xếp ba lô này dùng để giải bài toán trên có thể được diễn giải như sau trước tiên ta sắp xếp đồ vật theo thứ tự giảm dần về khối lượng. Tiếp đó ta lần lượt ta xếp vào mỗi ba lô một vật. Sau mỗi lần xếp người ta lại kiểm tra xem ba lô nào còn nhiều chỗ hơn thì sẽ được ưu tiên xếp trước. Tiếp tục quá trình như vậy ta sẽ nhận được một cách sắp xếp tối ưu. Về thuật toán tham ăn nội dung của nó là ta cứ xếp vào các ba lô cho đến khi không còn bỏ thêm được nữa sau đó thay đổi vị trí các đồ vật từ ba lô này sang ba lô kia để hợp lý hóa công việc sắp xếp xem 1 2 3 4 5 và tài liệu tham khảo ở đó . Trong bài này chúng tôi sử dụng một phương pháp trung gian lưu chuyển giữa hai thuật toán này. Trước khi sắp xếp chúng ta chọn ra những đồ vật nhỏ nhất gọi là tập hợp K với mục đích khi đã tham ăn tương đối đầy các ba lô thì ta dùng các đồ vật nhỏ từ K để tiếp tục chèn vào những lỗ hổng cho đến khi đầy ba lô. Một tập hợp các vật nhỏ như vậy được gọi là biểu diễn được đến k nếu các vật nặng từ 1 nhỏ đến k đủ nặng đều có thể biểu diễn được bằng tổng các đồ vật lấy từ tập K 2. Phát biểu bài toán Trước tiên chúng ta .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
165    62    3    28-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.