您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 交通运输 > 背包问题MATLAB程序
实验题目(1)物品数量为15,背包容量为120,物品价值分别为90,75,83,32,56,31,21,43,14,65,12,24,42,17,60物品重量分别为:30,27,23,24,21,18,16,14,12,10,9,8,6,5,3,2设计贪婪算法GA1或者GA2计算机程序解决该问题。GA1:(1)求解松弛问题,得关键项s。(2)当取11max,sjsjpp作为近似解值,即当11sjsjpp时,将第一个物品至第s-1物品放入包内;否则将第s个物品放入包内。GA2:(1)将物品按照价值密度从大到小的顺序放入包内,直到放不下为止;(2)将1中所得到得解值与物品的最大价值比较,取优者为输出。实验步骤及程序(1)新建M文件functiony=beibao(product,weight,value)fprintf('请输入数据(product,weight,value):\n');product=input('product=');weight=input('weighe=');value=input('value=');Total_value=0;Total_weight=30;fori=1:length(product),Total_value=Total_value+value(i);Total_weight=Total_weight-weight(i);if(Total_weight0)Total_value=Total_value-value(i);Total_weight=Total_weight+weight(i);elsechanpin_N(i)=product(i);chanpin_W(i)=weight(i);chanpin_V(i)=value(i);endenddisp('输出对应装入背包的产品号')chanpin_Ndisp('输出装入产品后背包总重量')sum(chanpin_W)disp('输出装入产品后背包总价值')sum(chanpin_V)end(2)点击运行,转换到窗口命令,输入数值即可运行结果请输入数据(product,weight,value):product=[123456789101112131415];weighe=[30272324211816141210986532];value=[907583325631214314651224421760];输出对应装入背包的产品号chanpin_N=1234007输出装入产品后背包总重量ans=120输出装入产品后背包总价值ans=301结果分析当装入1,2,3,4,7号物品时,总价值最大,为301,此时刚好达到背包总量上线。结果符合实际情况,故合理。
本文标题:背包问题MATLAB程序
链接地址:https://www.777doc.com/doc-6127195 .html