TAILIEUCHUNG - 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 .

• Toán học
• Phân hoạch tập các số tự nhiên
• Thuật toán xếp ba lô
• Thuật toán ăn tham
• Số nguyên dương
• Phương pháp giải toán
• Phương pháp giải toán Vật Lý 12
• Toán Vật Lý 12
• Phương pháp giải toán dao động điều hòa
• Phương pháp giải toán cộng hưởng cơ học
• Phương pháp giải toán truyền sóng cơ học
• Phương pháp giải toán giao thoa sóng
• Phương pháp giải toán đại số
• Phương pháp giải toán giải tích
• Giải toán giải tích
• Giải toán đại số
• Toán đại số
• Toán giải tích
• Bất phương trình
• Bất đẳng thức đại số
• Ứng dụng của đạo hàm
• Hệ phương trình mũ
• Giải toán trung học phổ thông
• Phương pháp giải toán trung học phổ thông
• Sử dụng phương pháp điều kiện
• Phương pháp lượng giác
• Phương pháp vectơ
• Phương pháp giải toán giải tích tổ hợp
• Giải toán giải tích tổ hợp
• Giải tích tổ hợp
• Phương pháp giải toán xác suất
• Giải toán xác suất
• Bài tập giải toán giải tích tổ hợp
• Phương pháp giải toán giải tích 12
• Giải toán giải tích 12
• Giải tích 12
• Phân dạng toán giải tích
• Ứng dụng đạo hàm
• Vẽ đồ thị của hàm số
• Hàm số logarit
• Phương pháp giải nhanh 999
• Giải nhanh 999 bài toán chọn lọc
• Bài tập Toán học
• Toán lượng giác
• Luận văn Thạc sĩ Khoa học ngành Toán sơ cấp
• Phương pháp toán sơ cấp
• Giải các bài toán không mẫu mực
• phương pháp quy nạp toán học
• Phương pháp phản chứng
• Phương pháp suy luận
• Phương pháp bảng
• Phương pháp sơ đồ
• Phương pháp đồ thị
• Giải phương trình
• TÍnh xác suất
• Toán cao cấp
• Phương pháp lập trình
• Phương pháp giải Toán cao cấp
• Phương pháp giải toán đa chiều
• Phương pháp giải toán đa biến
• Sách Toán học
• Tài liệu ôn tập môn Toán
• Phương pháp giải phương trình
• Phương pháp giải hệ phương trình
• giải bài toán bằng phương pháp véc tơ
• Phương trình vô tỉ có tham số
• Trắc nghiệm phương trình vô tỉ
• Giải hệ phương trình
• Hệ bất phương trình
• Phương pháp giải hệ bất phương trình
• Bài toán hệ phương trình
• Tính chất nghiệm
• Tính chất tham số
• Luận văn Thạc sỹ Toán học
• Phương pháp giải phương trình bất phương trình
• Phương trình bất phương trình chứa logarit
• Giải bài tập Toán 9
• Giải bài tập SGK Toán 9
• Hệ hai phương trình bậc nhất hai ẩn
• Giải bài tập SGK Toán 9 trang 16
• Bài tập giải hệ phương trình
• Giải hệ phương trình bằng phương pháp thế
• Giải bài tập SGK Toán 9 trang 19
• Giải bài tập hệ phương trình
• Giải hệ phương trình bằng phương pháp cộng đại số
• Phương pháp giải toán Hình giải tích
• Giải toán Hình giải tích
• Hình giải tích
• Hình giải tích trong không gian
• Giải toán Hình giải tích trong không gian
• Bài toán mặt cầu
• Bài toán hình học không gian
• Phương pháp tư duy giải nhanh toán
• Giải nhanh toán trắc nghiệm
• Phương pháp giải nhanh phần mũ
• Bài toán logarit
• Phương pháp giải nhanh phần nguyên hàm
• Tư duy giải nhanh phần số phức
• Bài toán Sinh học
• Phương pháp giải bài toán Sinh học
• Giải bài toán bằng máy tính cầm tay
• Phương pháp giải bài tập Sinh học