背包问题与公开密钥.pdfVIP

维普资讯 26 中学数学 2000年第1期 背包问题与公开密钥 100037 首都师范大学 周春荔 宁国然 例1 给出如下1O个自然数，6907，73，769， 的各种选法有2，1个，要确定是否有解，一般必需检验 3043，19，1480，373，41321，21768，178． 每种(m，m，…，％)所取的对应值 请你说出25758是其中哪几个数之和? m1a1+m2a2+…+鹕 用观察、心算凑数的方法很容易找出问题的答 是否等于 而2，l是随 指数增大的，当相当大时， 案：21768+3043+769+178之和恰等于25758． 就是用最快的电子计算机去算也难以完成! 这是第五届华罗庚金杯少年数学邀请赛的一道 于是，人们选择了背包问题中的一种特殊情况加 口试题．是由中国科学技术大学研究生院的裴定一教 以研究，也就是当所给的 个正整数a，a，…，满 授提供的．他说：这个问题的实际背景是“背包问题”． 足条件(*)：a1a2，a1+a2a3， 背包问题在公开密钥密码体制中是很有用的． a1+a2+a3a4，…，a1+a2+…+ 一1 那么，什么是背包问题呢?我们先从一个更为简 时，有一种快速寻求背包问题解答的程序．于是人们 单的实际例子谈起． 把满足条件(*)的背包问题，称为简单背包问题．简 例2 有6块矿石标本和一个背包，这6件标本 单背包问题的解法程序是： 的重量分别是lkg、3kg、5kg、lOkg、21kg、41kg．背包 设所给 个正整数不妨~t1／,到大排序就是 最多能装总重量为35kg的标本，你能从中选出若干 a1a2a3… 一1 ． 件标本恰装满总重量可容35kg的背包吗? 对所给正整数M，先求适合a≤Mak+的最 因为标本个数不多，只须观察就可找到答案：取 大下标志，再求适合条件a≤M_a +的最 lkg、3kg、lOkg、21kg四块标本装入背包就恰好满足 大下标志，如此继续下去，通过有限步之后，或者找到 要求． 一 个志f，使a=M—a^一a… ·一a^一1，或者没 显然，如果背包总容量可装36kg的标本，要从其 有这样的志“ 中找出若干块标本，使其总重量恰为36kg，是办不到 如果是前者，问题有解，取 的． 弛 =弛 一…一弛，一1，其余的弛一0， 就一般情况来说，问题可以如下提出： 这就找到了二值数组(m， ，…，％)． 一 只背包最多能装总重量为Mkg的标本，现共 如果是后者，则问题无解． 有 件标本，每件的重量均为正整数 ，它们是a， 按上述求解程序我们先解例2． a2，…，(kg)，而且a1+a2+…+ 试问：能 例2中，a1=1，a2=3，a3=5，a4=10，a5—21， 否从 件标本中选出若干件，使得被选出的标本的总 a6—41，显然 a1=13=a2， 重量恰为Mkg? a1+a2=1+3—45一a3， 如果被选出的标本记为1，未被选中的记为0，也 a1+a2+a3=1+3+5=910=a4， 就相当于判定是否存在取值为O，1的二值数组(m， a1+a2+a3+a4—1+3+5+1O m2，…，％)，使得 m1a1+m2a2+…+m．a= = 1921一a5， 因此，上述背包问题的数学模型是： a1+a2+a3+a4+a5—1+3+5+1O+21 若 个正整数a，a，…，和另一已知正整数 =4041=a6． M，满足a+口2+…+a 问：是否存在一个二 可见例2是个简单背包问题． 值数组(m1，m2，…，码。)(其中m／：0或1，i=1，2， 对于所给M：35kg，有 213541． … ， )，使得恰有m1a1+