0-1多项式背包问题是一类特殊而重要的整数规划问题，它可以定义为在0-1多维空间上极大化一个多项式函数的多约束(或单约束)最优化问题.由于这类问题在资源分配，工业生产及计算机网络的最优化模型中有着十分广泛的应用，因此研究0-1多项式背包问题的算法具有十分重要的现实意义.本文所讨论的0-1多项式背包问题可以描述如下： maxf(x)=n∑j=1cjxj+q∑i=1di∏j∈Nixjs.t.n∑j=1aijxj≤bi，i=1,…，m，x∈{0，1}n，其中，aij，cj，dj为非负实数，0＜bi＜∑nj=1aij，i=1，…，m，Ni(){1,…，n}且|Ni|≥2，i=1，…，q. 本文提出了0-1多项式背包问题的一种新的精确算法.该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法.我们用外逼近法求拉格朗日对偶问题得到上界，其中拉格朗日松弛问题通过转化为一个多项式时间可解的网络最大流问题来求解.为了提高算法的效率，我们利用两种启发式方法求初始可行解并用填充和交换的方法改进得到初始下界；并且在分枝定界前，利用所得到的拉格朗日界，先固定最优解中某些变量的值.数值结果表明本文提出的算法是有效的. 本文总共分为三章，第一章简单地介绍了0-1多项式背包问题的模型及应用.第二章简单介绍了求解0-1约束规划问题的现有算法，包括求解0-1二次背包问题的研究进展和超模背包问题的算法，最大流问题的算法第三章是我们的主要结果，提出了一种新的基于拉格朗日松弛和对偶搜索的分枝定界方法来求解单维和多维的0-1多项式背包问题，并给出了一个具体的例子.数值实验结果表明本文提出的算法是有效的.