算法分析与设计实验报告
第四次实验
//实现单位重量的平均价值 测试结果
sort(item,item+n,comparis on); 的物品的排序
{
if (item[i].w>c) break; tem[i]=1; c-=item[i].w; }
if (i<n) //物品只有部分被装下
tem[i]=c/item[i].w;
for (i=0;i<n;i++) //将排好序的物品编号与原始编号匹配 {
for (int j=0;j<n;j++) // 构造最优解 {
if (item[i].w==tmp[j])
x[j]=tem[i];
} }
待装物品的价值为：
选J 華装下的物品的比例如下：
111 = 1 [21 = 1
[33=0.664667
The time is 0-019请按任意键继绞・・•
for
(i=0;i<n;i++) //初始化数组x[]及tem[]
{x[i]=0,tem[i]=0;};
float c=m; for
(i=0;i<n;i++)
//物品整件被装下，则x[i]=1; 输入较小的结果:
F 算法二费法rQ-one2\D e bug\ce ro-o n&2 ■召Jew
待装物品
10 28 30
实验心得
助教签名
背包问题背包不同，物品可以部分的放入背包中，所
以思路也不一样，首先就是将物品按照单位质量价值排序，只这
一点就有一点难度。
难度在于要是排序后物品的编号就会发生改变，输出的就
不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们
的编号进行对比，就可以进行正确的输出了。
其中这个实验让我学
到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实
不会用；二十对于库函数sort函数的使用。
感觉每一次实验都有学到东西，很开心。
实验得分
附录：
完整代码（贪心法）
//贪心算法
#include <iostream> #include <algorithm> #inelude <time.h> #include <iomanip> using namespacestd;
const int N=10000;
floa v;
floa t w;
floa t
perval ;
};
void Knapsack( int n, float m,st item[], float x[]); // 声明贪心算法求解问题函数
int main()
{
float m;
int n,i;
cout<<"请输入背包的容量： ";
cin>>m;
cout<<"请输入物品的个数： ";
cin>>n;
st item[N];
float x[N+1];
cout<<"待装物品的重量为： "<<endl;
for (i=0;i<n;i++) cin>>item[i].w;
cout<<endl;
cout<<"待装物品的价值为： "<<endl;
for (i=0;i<n;i++) cin>>item[i].v;
cout<<endl;
// 计算每一个物品的单位重量的价值
for (i=0;i<n;i++) item[i].perval=item[i].v/item[i].w;
clock_t start,end,over; // 计算程序运行时间的算法 start=clock();
end=clock();
over=end-start; start=clock();
Knapsack(n,m,item,x); // 调用贪心算法函数
coutvv"选？择？装a ?下?的i??品？。
的i?d…•例Oy如…？下?: e o<<endl; //输出最优解编号及比例
for (i=0;i<n;i++)
//初始化数组x[]及tem[]
// 物品整件被装下，则 x[i]=1;
// 物品只有部分被装下
// 将排好序的物品编号与原始编号匹配
cout<<"["<<i+1<<"]:"<<x[i]<<endl; end=clock();
printf( "The time is %6.3f",( double )(end-start-over)/CLK_TCK); // 显 示运行时间
system( "pause");
return 0;
}
bool comparison(st a,st b){ // 自定义函数说明 sort 函数使用的形式是从大到 小排序
return a.perval>b.perval;
}
void Knapsack( int n, float m,st item[], float x[])
{
int i;
float tem[N]; // 该变量数组用来记录排好序之后的物品是否被放入背包 float tmp[N]; // 定义一个数组用来保存以前的编号及重量，用于构造最 优解 for (i=0;i<n;i++) tmp[i]=item[i].w;
sort(item,item+n,comparison); // 实现单位重量的平均价值的物品的排 序 for (i=0;i<n;i++) {x[i]=0,tem[i]=0;}; float c=m; for (i=0;i<n;i++)
{
if (item[i].w>c)
break; tem[i]=1; c-=item[i].w;
}
if (i<n)
tem[i]=c/item[i]
.w;
for (i=0;i<n;i++)
{
for (int j=0;j<n;j++) // 构造最优解
if (item[i].w==tmp[j])
x[j]=tem[i];。
