背包问题的若干性质及问题的简化

Some Properties of Knapsack Problem and Simplification of the Problem

对单约束线性整数规划(ILP,背包问题)的特性进行了分析,通过剪去无效变量对问题进行简化,并给出了问题的一个上界及最优值判定条件。

Some properties for the single restrict ILP（ Knapsack problem）are analyzed. Through cutting the invalided variable the Knapsack problem is simplified. An upper bound of this problem and a judge of the optimal value are given.