毕业论文背包算法

该算法是根据数学上的背包问题设计的。背包问题是一个最优化问题，即对一个给定空间或负重的背包和许多大小不一的物体，哪些物体放入背包才能使得浪费的背包空间或负重最小？在背包很小和物体数目较少时，这个问题还比较容易解决；但当背包很大且有很多个物体时，问题的求解就十分困难。通常，这个问题会有一个或者多个解，也有可能根本没有解。 1977年，Merkle与Hellman合作设计了使用背包问题实现信息加密的方法。其工作原理是：假定甲想加密，则先产生一个较易求解的背包问题，并用它的解作为专用密钥；然后从这个问题出发，生成另一个难解的背包问题，并作为公共密钥。如果乙想向甲发送报文，乙就可以使用难解的背包问题对报文进行加密，由于这个问题十分难解，所以一般没有人能够破译密文；甲收到密文后，可以使用易解的专用密钥解密。 该算法提出以后，经过多年的探讨和研究，最终发现了它的一个致命错误，使之失去了任何保密的实用价值。

1)登上算法用登山算法求解背包问题 function []=DengShan(n,G,P,W) %n是背包的个数，G是背包的总容量，P是价值向量，W是物体的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%输入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩余容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('装包的方法是');disp(X);disp(X.*W2);disp('总的价值是：');disp(P*X');时间复杂度是非指数的2)递归法 先看完全背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn, 每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。 本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x）=max{f(x-i)+c[i]} 当x>=w[i] 1<=i<=n 可使用递归法解决问题程序如下: program knapsack04; const maxm=200;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; function f(x:integer):integer; var i,t,m:integer; begin if x=0 then f:=0 else begin t:=-1; for i:=1 to n do begin if x>=w[i] then m:=f(x-i)+c[i]; if m>t then t:=m; end; f:=t; end; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); writeln(f(m)); end. 说明:当m不大时,编程很简单,但当m较大时,容易超时. 改进的递归法 改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个 一维数组即可 程序如下: program knapsack04; const maxm=2000;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; p:array[0..maxm] of integer; function f(x:integer):integer; var i,t,m:integer; begin if p[x]<>-1 then f:=p[x] else begin if x=0 then p[x]:=0 else begin t:=-1; for i:=1 to n do begin if x>=w[i] then m:=f(i-w[i])+c[i]; if m>t then t:=m; end; p[x]:=t; end; f:=p[x]; end; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); fillchar(p,sizeof(p),-1); writeln(f(m)); )贪婪算法改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选每一个数值，使得选中的数值的和正好等于背包的容量。代码思路：从最大的元素开始遍历超递增序列中的每个元素，若背包还有大于或等于当前元素值的空间，则放入，然后继续判断下一个元素；若背包剩余空间小于当前元素值，则判断下一个元素简单模拟如下：#define K 10#define N 10＃i nclude <>＃i nclude <>void create(long array[],int n,int k){/*产生超递增序列*/ int i,j; array[0]=1; for(i=1;i=0;i--)/*遍历超递增序列中的每个元素*/ { if(r>=array[i])/*如果当前元素还可以放入背包，即背包剩余空间还大于当前元素*/ { r=r-array[i]; cankao[i]=1; } else/*背包剩余空间小于当前元素值*/ cankao[i]=0; }}void main(){ long array[N]; int cankao[N]={0}; int i; long value,value1=0; clrscr(); create(array,N,K); output(array,N); printf("\nInput the value of beibao:\n"); scanf("%ld",&value); beibao(array,cankao,value,N); for(i=0;i＃i nclude <>void create(long array[],int n,int k){ int i,j; array[0]=1; for(i=1;i=0;i--) { if(r>=array[i]) { r=r-array[i]; cankao[i]=1; } else cankao[i]=0; }}int beibao1(long array[],int cankao[],long value,int n){/*贪婪算法*/ int i; long value1=0; for(i=n-1;i>=0;i--)/*先放大的物体，再考虑小的物体*/ if((value1+array[i])<=value)/*如果当前物体可以放入*/ { cankao[i]=1;/*1表示放入*/ value1+=array[i];/*背包剩余容量减少*/ } else cankao[i]=0; if(value1==value) return 1; return 0;}void main(){ long array[N]; int cankao[N]={0}; int cankao1[N]={0}; int i; long value,value1=0; clrscr(); create(array,N,K); output(array,N); printf("\nInput the value of beibao:\n"); scanf("%ld",&value); beibao(array,cankao,value,N); for(i=0;i=wi时： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式 当0<=j

首先建立一个堆栈，里面存放的是物品信息。算法开始后，按照一定的次序存放物品，每放进去一个物品，就检查是否越界，如果没越界，就继续选择物品放入（入栈）；如果越界，就退出当前物品（出栈），当正好装满一个背包时，记录当前栈到一个数组，并退出顶端物品（出栈），往后放物品……一直到栈空为止，这样可以找到所有最佳存放方法。