Tại sao không phải là vấn đề ba lô được bao gồm trong danh mục của thuật toán lập trình tuyến tính mặc dù thực tế là câu lệnh vấn đề Knapsack có vẻ tương tự như các vấn đề trong lập trình tuyến tính.?Tại sao giải quyết Knapsack probl. không được coi là lập trình tuyến tính?
Ba lô có thể được viết dưới dạng chương trình số nguyên tuyến tính. Không giống như lập trình tuyến tính bình thường, vấn đề này yêu cầu các biến trong giải pháp là số nguyên. Lập trình tuyến tính được biết là có thể giải được trong thời gian đa thức, trong khi lập trình tuyến tính nguyên là NP-complete.
Bài tập cho người đọc: cho thấy 3SAT có thể được giảm xuống thành lập trình tuyến tính số nguyên.
Thông tin bên lề: có các thuật toán xấp xỉ cho các vấn đề như MAX-3SAT (một biến thể của 3SAT mà chúng tôi muốn tối đa hóa số mệnh đề thỏa mãn). Trước tiên, bạn viết MAX-3SAT làm một chương trình tuyến tính số nguyên. Sau đó, bạn thư giãn nó thành chương trình tuyến tính, bằng cách xóa giới hạn số nguyên. Sau đó, bạn giải quyết chương trình tuyến tính trong thời gian đa thức. Cuối cùng, với thực x i ∈ [0,1], bạn tròn họ số nguyên, hoặc tạo ra giải pháp số nguyên ngẫu nhiên y i nơi khả năng của y i = 1 là x i.
Như là một bổ sung: http://stackoverflow.com/q/3128001/395857 –
Điều đáng lưu ý là nói chung nó thường tương đối dễ dàng để giảm vấn đề NP cho ILP. –
@ yes123 Trong lập trình tuyến tính, đó là các ràng buộc tuyến tính, không phải thời gian. – fgb