计算机求解背包问题的研究论文

下面是引用的一段说明，有背包问题的描述以及各种算法的代码，当然有些是VB的，有些是C＋＋的，我觉得听全面的，希望对你有所帮助。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较大时,容易超时. 4.2 改进的递归法 改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个 一维数组即可 程序如下: 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)); end. 3)贪婪算法 改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选每一个数值，使得选中的数值的和正好等于背包的容量。 代码思路：从最大的元素开始遍历超递增序列中的每个元素，若背包还有大于或等于当前元素值的空间，则放入，然后继续判断下一个元素；若背包剩余空间小于当前元素值，则判断下一个元素 简单模拟如下： #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

背包问题是组合优化学科中一个经典而著名的问题，它的研究价值不言而喻，吸引了众多专家学者从各个角度开展对其的研究工作，各种算法设计思想也应运而生。由于背包问题的NP完全性，如何在算法的时间效率和求解精度上取得有效的平衡，成为背包问题算法设计主要的考虑因素。数据挖掘是近几年信息领域发展最快的技术之一。由于数据挖掘具有强大的发现有用知识的功能，可以利用它来发现背包问题解的相似的状态空间，然后进行约减，从而克服背包问题的NP困难性。背包问题，是用来介绍动态规划算法最经典的例子，网上关于01背包问题的讲解也很多，我写这篇文章力争做到用最简单的方式，最少的公式把01背包问题讲解透彻。01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。Pi表示第i件物品的价值。决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？