为什么解决背包问题不被视为线性规划? [英] Why solving Knapsack problem is not considered as linear programming?

问题描述

尽管背包问题陈述似乎与线性规划中的问题相似，为什么背包问题不属于线性规划算法类别?

Why isn't the knapsack problem included under the category of linear programming algorithms in spite of the fact that the Knapsack problem statement seems similar to the problems in linear programming?

推荐答案

背包可以写为整数线性编程程序.与常规线性编程不同，此问题要求解中的变量为整数.线性规划在多项式时间内是可解的，而整数线性规划是NP完全的.

Knapsack can be written as an integer linear programming program. Unlike normal linear programming, this problem requires that variables in the solution are integers. Linear programming is known to be solvable in polynomial time, while integer linear programming is NP-complete.

供读者练习:表明3SAT可以简化为整数线性规划.

Exercise for the reader: show that 3SAT can be reduced to integer linear programming.

琐事:对于MAX-3SAT(3SAT的一种变体，我们希望最大程度地满足子句的数量)存在一些近似算法.首先，您将MAX-3SAT编写为整数线性程序.然后，通过消除整数限制，将其放松到线性程序.然后，您可以在多项式时间内求解线性程序.最后，给定实数x _i ∈[0,1]，将它们四舍五入为整数，或生成随机整数解y _i ，其中y _i = 1是x _i .

Trivia: there are approximation algorithms for problems such as MAX-3SAT (a variant of 3SAT where we want to maximize the number of satisfied clauses). First you write MAX-3SAT as an integer linear program. Then, you relax it to linear program, by removing the integer restriction. Then, you solve the linear program in polynomial time. Finally, given real x_i ∈ [0,1], you round them to integers, or generate random integer solution y_i where probability of y_i = 1 is x_i.

这篇关于为什么解决背包问题不被视为线性规划?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！