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

1楼的不是遗传算法吧！刚好做过这个遗传算法解背包问题的论文，给你回答啦~~独家哦，分数要给偶~~1、程序开发环境 开发环境：Visual C++6.0 (把Fortran程序改为VC) 操作系统：Windows 2003 Professional2、程序性能对比 运行时间与加速比（如表1所示）进程数p（个） 1 2 4 运行时间t（秒） 129s 78s 38s 加速比s 1.65 3.38 表1、运行时间与加速比3、程序运行结果： 实例数据： 假设物体的重量Weight、物体的收益Profit和背包的容量Contain 分别为：Weight={ 80，82，85，70，72， 70，66，50，55，25 ， 50，55，40，48，50， 32，22，60，30，32 ， 40，38，35，32，25， 28，30，22，50，30 ， 45，30，60，50，20 ， 65，20，25，30，10 ， 20，25，15，10，10 ， 10，4， 4， 2， 1 }Profit={ 220，208，198，192，180， 180，165，162，160，158， 155，130，125，122，120 ， 118，115，110，105，101， 100，100，98， 96， 95， 90， 88， 82， 80， 77 ， 75， 73， 72， 70， 69， 66， 65， 63， 60， 58， 56， 50， 30， 20， 15， 10， 8， 5， 3， 1}Contain=1000， 如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大? 传统的算法（动态规划、递归回溯法和贪心算法所得结果： 总价值为3077 , 总重量为999。 2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果 总价值为3103, 总重量为1000。 我们算法所得结果： 总价值为3103, 总重量为1000。 我们所求得最优解的个体分配情况为：11010 10111 10110 11011 01111 11101 00001 01001 10000 01000算法 最大迭代次数 总价值为 总重量为 传统的算法 400 3077 999 佳点集算法 70 3103 1000 遗传算法 75 3103 1000 // knapsack.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include #include #include #include #include #include // 重要常量参数#define popsize 200 //种群的规模#define pc 0.618 //杂交概率#define pm 0.03 //变异概率#define lchrom 50 //染色体长度#define maxgen 1000 //最大进化代数struct population{ unsigned int chrom[lchrom]; //染色体 double weight; //背包重量 double fitness; //适应度 unsigned int parent1,parent2,cross; //双亲、交叉点};//新生代种群、父代种群struct population oldpop[popsize],newpop[popsize]; //背包问题中物体重量、收益、背包容量int weight[lchrom],profit[lchrom],contain; //种群的总适应度、最小、最大、平均适应度 double sumfitness,minfitness,maxfitness,avgfitness;//计算适应度时使用的 惩罚函数系数double alpha;//一个种群中最大和最小适应度的个体int minpop,maxpop; /* 读入背包信息,并且计算惩罚函数系数 */void read_infor(){ FILE *fp; int j; //获取背包问题信息文件 if ((fp=fopen("knapsack.txt","r"))==NULL) { //读取文件失败 AfxMessageBox("The file is not found",MB_OK,NULL); return; } //读入物体收益信息 for (j=0;jmaxfitness)&&((int)(tmp_fit*10)%10==0)) { maxfitness=pop[i].fitness; maxpop=i; } //选择种群中最小适应度的个体 if (tmp_fitoldmax) { report(newpop,gen); } //保存新生代种群的信息到老一代种群信息空间 memcpy(&oldpop,&newpop,popsize*sizeof(struct population)); } printf("It is over."); getch();}

下面是引用的一段说明，有背包问题的描述以及各种算法的代码，当然有些是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件物品应该放入背包中吗 ？