We address a variant of the continuous knapsack problem, where capacities regarding costs of items are given into account. We prove that the problem is NP-complete although the classical continuous knapsack problem is solvable in linear time. For the case that there exists exactly one capacity for all items, we solve the corresponding problem in O(nlog n) time, where n is the number of items.
Quoc, H.D., Kien, N.T., Thuy, T.T.C., Hai, L.H. and Thanh, V.N., 2018. Inverse version of the kth maximization combinatorial optimization problem. Can Tho University Journal of Science. 54(5): 72-76.
Tạp chí khoa học Trường Đại học Cần Thơ
Lầu 4, Nhà Điều Hành, Khu II, đường 3/2, P. Xuân Khánh, Q. Ninh Kiều, TP. Cần Thơ
Điện thoại: (0292) 3 872 157; Email: tapchidhct@ctu.edu.vn
Chương trình chạy tốt nhất trên trình duyệt IE 9+ & FF 16+, độ phân giải màn hình 1024x768 trở lên