摘要
in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.
in this paper, the approximation for four kinds of knapsack prob- lems with multiple constraints is studied: 0/1 Multiple Constraint Knapsack Problem(0/1 MCKP), Integer Multiple Constraint Knapsack Problem (Integer MCKP), 0/1k-Constraillt Knapsack Problem (0/1 k-CKP) and Integer k-Constraint KnapsackProblem (Integer k-CKP). The following results are obtained:1) Unless NP = co - R, no polynomial time algorithm approximates 0/1 MCKPor Integer MCKP within a factor k(1/2)- for any > 0; unless NP = P, nopolynomial time algorithm approximates 0/1 MCKP or integer MCKP within afactor k(1/4)- for any > 0, where k stands for the number of constraints.2) For any fixed positive integer k, 0/1 k-CKP has a fully polynomial time approximation scheme (FPTAS).3) For any fixed positive integer k, Integer k-CKP has a fast FPTAS which hastime complexity O(n +) and space complexity O(n + (1/3)), andfinds an approximate solution to within 5 of the optimal solution.
