中文摘要：

子集和问题是计算机科学中的一个重要问题,也被应用于公钥密码和伪随机函数的设计.学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法.本文通过建立子集和问题和联立丢番图逼近问题之间的联系,提出一种新的子集和问题启发式求解算法.该算法由给定的子集和问题构造联立丢番图逼近问题,使用格归约算法寻找该联立丢番图逼近问题的解,由此构造与原始子集和问题线性无关的新的子集和问题,从而达到降低原始子集和问题维数的目的;最后,通过n-1个联立丢番图逼近问题的解来构造n—1个线性无关的子集和问题,并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题.基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.