Thông tin chung:

Ngày nhận bài: 04/05/2019
Ngày nhận bài sửa: 27/07/2019

Ngày duyệt đăng: 30/10/2019

Title:

A linear time algorithm for the balanced {0,1}-knapsack problem

Từ khóa:

Bài toán cân bằng, bài toán xếp ba lô, quy hoạch động

Keywords:

Balance problem, dynamic programing, knapsack problem

ABSTRACT

In this paper, a variant of the balanced optimization problem, where the knapsack constraint is associated, is considered. To solve this problem, a special structure of the feasible solutions is explored. Based on this investigation, a dynamic approach is developed to solve the mentioned problem in linear time.

TÓM TẮT

Trong bài báo này, một biến thể của bài toán tối ưu cân bằng với ràng buộc có dạng xếp ba lô được nghiên cứu. Để giải quyết bài toán, một cấu trúc đặc biệt của tập các phương án chấp nhận được chỉ ra. Dựa vào đó, một thuật toán quy hoạch động được đề xuất để giải bài toán đã nêu trong thời gian đa thức.

Trích dẫn: Võ Nguyễn Minh Hiếu, Trần Thủ Lễ và Nguyễn Ngọc Đăng Duy, 2019. Thuật toán quy hoạch động cho bài toán xếp ba lô cân bằng {0,1}. Tạp chí Khoa học Trường Đại học Cần Thơ. 55(5A): 82-87.