背包问题matlab程序.doc

《背包问题matlab程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验题目（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）当取作为近似解值，即当时，将第一个物品至第s-1物品放入包内；否则将第s个物品放入包内。GA2：（1）将物品按照价值密度从大到小的顺序放入包内，直到放不下为止；（2）将1中所得到得解

2、值与物品的最大价值比较，取优者为输出。实验步骤及程序（1）新建M文件functiony=beibao(product,weight,value)fprintf('请输入数据（product,weight,value）:');product=input('product=');weight=input('weighe=');value=input('value=');Total_value=0;Total_weight=30;fori=1:length(product),Total_value=Total_value+

3、value(i);Total_weight=Total_weight-weight(i);if(Total_weight<0)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

4、(chanpin_W)disp('输出装入产品后背包总价值')sum(chanpin_V)end（2）点击运行，转换到窗口命令，输入数值即可运行结果请输入数据（product,weight,value）:product=[123456789101112131415];weighe=[30272324211816141210986532];value=[907583325631214314651224421760];输出对应装入背包的产品号chanpin_N=1234007输出装入产品后背包总重量ans=120输出装入产品

5、后背包总价值ans=301结果分析当装入1，2，3，4，7号物品时，总价值最大，为301，此时刚好达到背包总量上线。结果符合实际情况，故合理。