加权set packing问题的精确算法

加权set packing问题是组合优化中一个经典的NP-hard问题,在现实中具有广泛的应用。针对加权set packing问题本文首先研究了其数学性质,利用数学性质约简问题的规模,并在此基础上提出了上下界子算法;然后根据数学性质和上下界子算法设计了求解该问题的回溯算法;最后应用加权分治技术将算法的时间复杂性从传统分析下的O(1.38028^(k))降为O(1.32401^(k)),并进行了算法对比分析。结果表明利用加权分治技术可以有效降低算法的时间复杂性。