组合优化（也称为离散优化），是应用数学的一个活跃领域，它把组合数学、线性规划以及算法理论的技术结合起来解决离散结构上的最优化问题。组合优化是运筹学中的一个重要分支，所研宄的问题涉及经济管理、后勤管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术、控制论及军事运筹等诸多领域。本文中所涉及到的0-1背包问题、多维背包问题、旅行商问题等都是组合优化的基本问题。然而下模性概念在19世纪就已经提出,当时Edgworth和Pareto主要倡导这一概念.在组合优化问题中，很多具体问题的目标函数都包含下模性，因此，下模集函数在求解组合优化问题中有很重要的作用。另一方面,基于下模性在优化算法设计中的良好性质，它在理论计算科学领域占具很重要的作用。下模集函数最大值问题具有十分重要的理论意义和实际应用价值，所以一直以来它被许多理论研宄学者广泛地研宄着,同时也取得了很多重要的成果。本文简要介绍了组合优化基本理论，即组合优化概述、定义及其问题实例。算法概述及其算法复杂性，组合优化问题复杂性，并将组合优化问题复杂性进行了分类。对于大多数组合优化问题来说都是M5难问题，一般没有很好的有效的求解方法，特别是多项式时间算法，因此，人们退其次而求之，主要去寻找求解此类问题的相对有效的近似算法。许多人的研宄主要致力于设计怎么样的算法，使得所设计的算法具有相对较好的性能保证，从而更加有效的解决实际生活中的组合优化问题。文章介绍贪婪算法的基本原理，同时结合背包问题的特点。介绍了背包问题与下模函数的关系，随后给出了下模函数的概念及其基本性质。最后利用贪婪算法求解d-Knapsack Problem,并说明了其性能保证。全文共分五章，第一章绪论简述了组合优化问题及其基本概念，然后给出了组合优化问题的实例，研宄背景，最后给出了本文任务。第二章综述了算法复杂性及其问题复杂性，贪婪算法基本原理及其算法描述及其研宄现状、在组合优化问题中的广泛应用。第三章介绍了近似算法及其性能保证。第四章介绍了下模函数以及相关概念和性质。第五章给出了d-KnapsackProblem的求解算法，并从理论上分析其算法的性能保证及其合理性。