摘要：贪心算法是一种容易理解简单的算法，在解决最优化问题时是人们的首选算法，本文着重介绍了贪心算法的具体内容，并对0/1背包问题运用贪心算法进行求解，由于贪心算法只能得到局部最优解，不能够得到全局最优解，于是对贪心算法做了进一步的改进，使求得的解能更进一步的接近最优解。83873

毕业论文关键词：贪心算法；0/1背包问题；K阶优化方法

The Greedy Algorithm to Solve 0/1 Knapsack Problem

Abstract: The greedy algorithm as a simple algorithm in solving the optimization problem is people's choice Algorithm, this article focuses on the specific content of the greedy algorithm, and uses the greedy algorithm to solve the 0/1 knapsack problem, due to the greedy algorithm to be just local Optima, cannot get global optimal solutions, and made further improvements on the greedy algorithm, so that the solution can be obtained further near-optimal solutions。

Key words: The greedy algorithm; 0/1 knapsack problem; K order optimization methods

目    录

摘要 1

引言 2

1。 预备知识 3

2。 贪心算法 4

2。1贪心算法的概念 4

2。2贪心算法的基本思想 4

2。3贪心算法的基本要素 4

2。4贪心算法适用问题类型 5

2。5贪心算法的解题步骤 5

2。6解题注意要素 6

2。7贪心策略 7

3。 0/1背包问题 7

3。1 问题描述 7

3。2 贪心算法求解0/1背包问题 8

3。3 贪心算法的不足 9

4。 改进的贪心算法 10

5。 结束语 11

参考文献 13

致谢 14

基于贪心算法求解0/1背包问题

引言

不论是日常生活还是生产中，解决问题时我们总希望能找到一个最优的解决方法，既能做到时间最快，又能获得最大的价值，贪心算法是指从起始状态开始，通过几个贪婪的选择，采用一种迭代的方式，自上而下逐次进行贪婪的选择，对所需的一个较小的子问题，需要一步一步的贪心选择。通过贪婪的选择，最终我们可以得到一个最佳的解决方案，以获得最佳值（或更好的解决方案）一类的问题求解方。贪心算法的操作过程简单，不浪费过多的存储空间和时间，并能在很多情况下得到最优解。日常生活中的许多优化问题都是类似的背包问题，希望能充分利用现有的空间，资源，不浪费，可以得到最大的价值。 贪心算法是作为一种解决最优化问题的方法，可以得到一些问题的全局最优值和相应的全局最优解。本文中根据参考文献[1]-[4]详细的介绍了贪心算法的概念，基本思想，要素，和贪心算法可以解决的问题类型及解决步骤。并且根据参考文献[5]-[11]系统的阐述了0/1背包问题，我们运用贪心算法中所涉及到的单位价值优先策略解决了0/1背包问题。文献综述

贪心算法没有从总体上进行考虑，这也就使得用贪心策略求解得到的只是所求问题的局部最优解，并不一定能够得到所求问题的全局最优解。 在本文中，我们由参考文献[12]对贪心算法做了进一步的改进，得到一种改进的贪心算法—K阶优化方法，K阶优化方法虽然也不一定能得到最优解，但它能使得到的解在最优值的( 100 ( k +1) ) %内，能更好地接近最优解。