实验题目
(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)当取
1
1
max ,
s
j s
j
p p
作为近似解值,即当
1
1
s
j s
j
p p
时,将第一个物品至第 s-1 物
品放入包内;否则将第 s 个物品放入包内。
GA2
:
(1)将物品按照价值密度从大到小的顺序放入包内,直到放不下为止;
(2)将 1 中所得到得解值与物品的最大价值比较,取优者为输出。
实验步骤及程序
(1)新建 M 文件
function y=beibao(product,weight,value)
fprintf(' 请输入数据( product,weight,value ) :');
product=input('product=');
weight=input('weighe=');
value=input('value=');
Total_value=0;
Total_weight=30;
for i=1:length(product),
Total_value=Total_value+value(i);
Total_weight=Total_weight-weight(i);
if(Total_weight<0)
Total_value=Total_value-value(i);
Total_weight=Total_weight+weight(i);
else
chanpin_N(i)=product(i);
chanpin_W(i)=weight(i);
chanpin_V(i)=value(i);
end
end
disp('输出对应装入背包的产品号 ')
chanpin_N
disp('输出装入产品后背包总重量 ')
sum(chanpin_W)
disp('输出装入产品后背包总价值 ')
sum(chanpin_V)
end