背包算法的原理与程序设计

摘 要
本文主要是对背包问题进行简单的研究和程序设计，首先从背包问题的提出和背包问题的研究意义出发，浅谈背包问题的应用前景。背包问题因其设计简单并且能有一个私钥对多个公钥的设计，可以使其在未来的发展上拥有更大的使用空间。背包问题一般分有两种，一种是加法背包，一种是乘法背包。本文主要研究的是加法背包。解决加法背包问题的方式有很多种，一般最基本的就是动态规划法和贪心算法。动态规划法通常以自底向上的方式解各子问题。贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择。解题步骤为1、建立数学模型描述问题。2、把求解问题分成若干子问。3、对每一子问题求解，得到子问题的局部最优解。4、把子问题的解局部最优解合成原来解问题的一个解最后，动态规划算法的精确算法,从整个问题的最优解的问题一步一步构造,最佳的解决方案,但缺乏整体检验能力,算法只适用于较小的问题。贪婪算法属于近似算法,然而,虽然速度快,更少的时间消耗,但不一定是最优的解决方案,解决问题的有效性。研究背包问题以及解决背包问题应该要根据具体问题来具体分析。通过多方面考虑，选择合适的算法进行解析，才能得出最终答案。
关键词 ：java；程序；背包；贪心
?
Abstract：
This article is mainly to simple the knapsack problem research and program design, first of all from the knapsack problem is put forward and the research significance of knapsack problem, discuss the application prospect of knapsack problem. Knapsack problem because of its simple design and can have a private key to the design of multiple public key, you can make it on the future development of a greater use of space. Knapsack problem generally there are two points, one is add backpack, backpack is a kind of method. This paper mainly studies the addition backpack. To solve knapsack problem with addition, there are many ways of usually is the most basic of dynamic programming and greedy algorithm. Dynamic programming solution in a bottom-up way usually each sub-problem. Greedy algorithm is usually in a top-down manner, made in the form of iteration successively the greedy choice. The problem solving steps 1, establishing the mathematical model to describe problems. 2, the solving problem into several sub asked. 3, for each problem solving, the local optimal solution of the problem. 4, the solutions to the sub-problems local optimum synthesis of the original solution a solution of the problem in the end, accurate algorithm of dynamic programming algorithm, from the whole issue of the optimal solution of problem step by step, to construct the best solution, but lack the overall inspection ability, algorithm applies only to smaller problems. Greedy algorithm belongs to the

approximate algorithm, however, although the speed is quick, less time consumption, but not necessarily the most optimal solution, the effectiveness to solve the problem. The knapsack problem and solving knapsack problem should be concrete analysis according to concrete problems. Through various consideration, choosing the appropriate parsing algorithm, can be concluded that the final answer.
Keywords：Java ，backpack program，greedy
1引 言
背包算法是世界上第一个使公钥密码体制成为现实的密码算法，它说明了如何将数学上难以解决的问题应用到公钥密码算法的设计当中。背包体制的优势是加解密的速度很快，不过花无百日红，它在提出两年后就被人们破译了，故而它的安全性太低使其不能用于商业目的[1]。研究背包算法，可以将密码学的学习更加深化。
2公钥密码体制的基本原理
非对称密码体制(非对称加密系统),通常也被称为公钥密码系统，或者双钥密码体制，是由于对称密码体制本身具有一定的缺陷而推出的。只要有一个公钥,所以可以加密的信息。公钥以及私钥有相互依存的关系,用户只有私钥解密信息,甚至没有授权用户没有办法发送信息解密加密的信息。公钥加密算法最大的特点是使用两个相互对应的关键k =(pk,sk)分别进行加密和解密的过程。当两个用户想要使用的公钥系统开始秘密通信、传输与接收A方B方的pk信息加密和公钥发送到接收机,接收B方就可以使用对应A方的公钥或者私钥sk解密信息。公共或者私有密钥需要相互对应,只有当使用相对应的公钥加密用户私钥可以正确解密,从而得出正确的明文。因为私钥的接收者单独沟通,其他用户不知道,所以只能接收B方正确恢复出清晰的信息,即使其他用户访问密码短信不能算出正确的清晰,从而完成秘密通信。常用的公钥加密算法有: 拉宾算法；背包算法；RSA公开密钥算法；以及椭圆曲线算法和EIGamal算法等等[6]。公钥加密系统具有以下优点: 1.密钥的分配简单， 2.密钥的保存量少， 3.可以满足互不相识的双方相互间进行保密的通信需求， 4.完成数字签名和数字鉴别[6]。
3背包问题
3.1 背包问题的提出以及所要研究的意义
3.1.1 背包问题的提出
背包问题是Hellman和Merkel在1978年提出来，背包算法来源于著名的背包问题（knapsack problem），属于一种组合优化的N P完全问题。就是在放在包里的物品重量不能超过最大值的前提下，背包里面的物品价值的和是否可以达到最大V。
3.1.2背包问题的研究意义
背包问题的工作原理是:假如有一个人A想为某种东西加密，则先产生一个比较容易求解出来的背包问题，并用它的解作为该东西的专用密钥，然后基于这个问题，再生成另一个相对来说比较难解的背

包问题，并作为公共的解题密钥。如果有另一个人B想向A发送加密的报文，B就可以使用这个难以解开的背包问题对想发送的报文进行加密，由于这个问题比较难解，所以一般没有人能够破译它的密文，A收到密文后，就可以使用之前相对来说比较易解的专用密钥来进行解密。相似问题经常出现在计算组合数学、复杂性理论、商业、和密码学以及应用数学等领域中。研究背包问题可以解决各领域内的有上限值的加密问题。将各元素排列组合可得到多种方式，但是经过优化后，组合的数量就是相对而言较少的了，而优化的方式不同，得出的组合顺序也不同，在大多数人都知道元素的情况下，使用特殊的优化方式，便可成为一套自己的密码，这样便可达到加密的安全作用。背包问题的研究具有十分重要的现实意义 ,这不仅因为问题的算法有一个简单的结构,可以作为理论基础,理论中一个困难的问题很有研究价值,更重要的是,因为它是在很多实际应用也可以通过该算法。背包问题大多数来说是不可以算出来的问题，背包体制以其加密的速度还有解密的速度非常的快而受人关注。但是，现在很少有人使用背包体制来进行加密，因为大多数一次背包体制都能够被破译了。简而言之,背包问题是给定条件下的极限,可以达到的最大好处的问题[4]。背包算法的早期应用之一是，在测试生成和得分，测试人员可以选择哪些问题来回答。对于一个小例子，这是测试人员提供这种选择的一个相当简单的过程。背包问题求解方法的研究已经成为许多现代科学的焦点,它在现实生活中得到了较大范围的应用。但由于一些问题计算远远超出有效时间的计算机的能力,解决问题变得异常困难。特别是对于NP完全问题如何解决最优解或近似最优解被选为科学家们关注的焦点之一。
3.1.3基础背包问题
背包问题的基础问题是：有n个东西，可放进一个背包里，可是背包的的承重力是W，物品的重量是W i，价值是v [ i ]。将哪些物品装入背包可以使这些物品的重量不可以超出背包的总容量，还能有最大的物品价值。其特点是:每一个物品都只能呢个选择放进背包或者舍弃。在数据结构算法的学习中，解决背包问题是一种最基本的,伴随着深化的学习Java,首先要学会会建立一些算法编程实现,提高自身水平,首先结合分析数据和练习编程来解决背包问题。
4 背包算法
4.1 背包算法的分类以及编译方法
背包算法主要分为几类：
1）加法背包算法。假设给定一些按从小到大排列的数字。如果前面几个的数加起来的和总小于接下来的那个数，那么这些数就可以构成一个背包，我们给定某数作为背包里

面的 某一些数的总 和，这个数就为被 加密的数，由这个背包组成这个数只有一种组合方式，这个方式 就是秘密了[2]。
2）乘法背包算法。乘法背包相对加法背包来说更复杂，不仅是运算的数量大了很多，并且你得到的一个已加密了的数据更加大，一般来说都是上亿[2]。用乘法背包算法来加密，数字的增长很快的，背包特点为:如果把背包里面的数据从小到大，那么，前面所有数据的乘积小于后面的任何一个元素。
现已经有多种方式进行加密和破解。所以随着时代的发展和进步，人们对背包算法的改进越来越多，使其更加精密安全。而与之随来的是破解的方法也在进步发展。
4.2 加法形式的背包算法
即：给定一组重量和价格都不同的物品，要选取其中部分物品放进一个有重量上限的背包，我们只能选择要（1）或者不要（0）,不能够将他们拆分。这个问题有两个条件需要考虑：1)放置的物品总重量应小于等于背包可以承载的大小。2）物品的总价值必须要尽量大。我们应该要怎么选择，才能使物品的总价最大。
解决加法背包算法可选两种方式：贪心算法或者动态规划算法。
1）动态规划算法一般以自底向上的方式来解决各子问题，先得到该问题的局部解然后扩展到全局问题的解。 动态规划一般遍历二叉树便可一目了然的看到选择的过程。基本实践是深度优先搜索,它是一种通过枚举每个搜索算法和检验的问题。它的基本思想是:改变道路路,直到可以通过马路。这种方法的组织法和图表法通常用于组织。所需解决的问题需要被转换成状态空间树可以解决的。
动态规划用来解决问题,一般需要三个步骤:首先,要明确你的解决方案空间所需要解决的问题;其次,找出一个解决方案空间结构,以便搜索;最后,用一个方法称为深度优先搜索解空间,需要修剪函数,所以不存在搜索不到的想象。
（公式3.1）
（公式3.2）
上面的两个公式分别是背包问题的子集和问题的目标函数、约束条件，而动态规划方法的递推公式（公式3. 3）和边界条件（公式3.4-公式3.6）：
（公式3.11.3）
, 对一切y, （公式3.11.4）
, 对一切y, （公式3.11.5）
（公式3.11.6）
此外,通过动态规划算法来解决这个问题,如果将它们拆分成若干子问题,那么得到子问题是相互独立的。当我们得到这些子问题的解决方案,我们可以将其保存,当需要正确的答案,这样就可以不用计算,节省大量的计算时间。动态编程算法已经应用于很多领域,如在计算两个时间序列的距离,分配资源的利用率,排序顺序,货物装载,项目管理,解决最短路径问题的动态规划算法需要将优先考

虑使用动态编程算法,因为该算法不仅是简单和容易理解的原理,而且算法的思想是非常清楚的,因此,许多工人可以很容易地通过所需的动态规划算法来解决问题。
2）贪心算法则一般以自顶向下的方式进行计算，以迭代的方式做出头尾相连的贪心选择。贪心算法有自己的一套方式解决问题,它总是在当前形势下是最好的选择。也就是说,不是作为一个整体考虑,它能做的最好的就是只有在某种意义上的局部最优解。从当地的贪婪算法与每个研究,然后获得整体的最优解。使用贪婪算法,通常可以找到最优解的测量标准,和衡量标准,那么它必须通过经验和猜测。按照这一标准,不需要花多少时间能找到最优解,每一步从局部最优解,所以整体的最优解也是显而易见的,直接替代那些不符合标准的。不是对所有问题来说，运用贪心算法都能得到整体的最优解,但范围很大的问题它可以产生整体最优解或最近似最优解的解。主要步骤如下：
1.建立数学模型描述问题
2.把求解问题分成若干子问题
3.求解每一子问题，得到该子问题局部的最优解。
4.把局部子问题的解最优解来解原来解问题
贪心算法可以做以下三种分析策略：
１.选择所有物品里面价值是最大的那个物品，这样可以尽可能快速的增加总价值。但是，虽然每一次做出的选择都使得背包的价值的最大值的增长，但背包容量却可能因此消耗的更快，使得我们装入背包的所选物品个数上限降低，这样就不能保证最终结果能达到最大值。每作次贪心选择就让所求的背包问题简化为相对前次规模更小的子问题。
２.选择所有物品里面重量最轻的物品，因为这可以尽可能多的装入物品，从而一步步增长背包的总价值，但是，虽每一步选择都能使背包的容量消耗慢了，但背包的价值却没能保证达到很迅速增长，从而不能保证最终结果达到最大[3]。
３.上面两种贪心策略或只想到背包价值增长，或只想到背包容量消耗。但为了得到所求背包问题最优解法，需要在背包价值增长与容量消耗二者之间寻找到一定的平衡。正确贪心策略应该是选择单位重量和价值最大的物品。
5 背包算法的程序设计
若假定有一个小偷进了一个业主的家里，去的时候他自己只带了有一个最大负载量为20kg的背包，业主家里有很多种东西，但是小偷只能选择几样，所以小偷要选择向内放入N种物品，使得其的总价值最大。
备选的物品为：
表5.1
A B C D E F
V（$） 12 14 10 5 4 7
W(kg) 7 10 8 4 1 3
1） 通过动态规划分析，
图5.1
图5.2
可得以下组合方式：
可以得出三字密码：ABF（w=20 v=33） ACD(w=20 v=29) BCE (w=19 v=28)
四字密码为： BDEF(w=19 v=30) CDE