算法分析与设计实验报告
第四次实验
姓名
学号
班级
时间
上午
地点工训楼309实名称贪心算法实验(求解背包问题)
实验目的
通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。
实验原理
给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。
程序思路：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
x[j]=tem[i];
}
}
}
测试结果
输入较小的结果：
输入较大的结果：
实验心得
首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西，很开心。
实验得分
助教签名
附录：
完整代码（贪心法）
;
cout<<endl;
cout<<"待装物品的价值为："<<endl;
for(i=0;i<n;i++)
cin>>item[i].v;
cout<<endl;
erval=item[i].v/item[i].w;
clock_t start,end,over; ;
sort(item,item+n,comparison); >c)
（4）依此策略一直地进行下去，直到背包装满为止。
关键代码
boolcomparison(st a,st b){ ;
sort(item,item+n,comparison); >c)
break;
tem[i]=1;
c-=item[i].w;
}
if(i<n) ;
for(i=0;i<n;i++) ==tmp[j])
break;
tem[i]=1;
c-=item[i].w;
}
if(i<n) ;
for(i=0;i<n;i++) ==tmp[j])
x[j]=tem[i];
}
}
}
（1）首先将单位重量的平均价值排序。
（2）根据背包容量依次将平均价值高的物品放入背包中。
实验步骤
（1）首先计算每种物品单位重量的价值vi/wi；
（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；
（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；