贪心算法实验（求解背包问题）

算法分析与设计实验报告

第 四 次实验

姓名 时间 学号 地点 班级 工训楼309 10.17上午 实验名称 贪心算法实验(求解背包问题) 实验目的 通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。 实验原理 给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。 程序思路： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 （1） 首先将单位重量的平均价值排序。 （2） 根据背包容量依次将平均价值高的物品放入背包中。 （1）首先计算每种物品单位重量的价值vi/wi； （2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包； （3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包； （4）依此策略一直地进行下去，直到背包装满为止。 实验步骤 关键代码 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;ic) break; tem[i]=1; c-=item[i].w; } if(i

附录：

完整代码（贪心法）

//贪心算法 背包问题

#include #include #include #include using namespace std;

const int N=10000;

struct st{ //定义结构体，用来存放和物品相关的变量 float v; float w; float 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<<\待装物品的重量为：\<>item[i].w; cout<

cout<<\待装物品的价值为：\<>item[i].v; cout<

//计算每一个物品的单位重量的价值 for(i=0;i

Knapsack(n,m,item,x); //调用贪心算法函数

cout<<\选?择?装á??下?的ì?物?品?¤的ì?比ਨ例¤y如¨?下?：êo\<

end=clock();

printf(\,(double)(end-start-over)/CLK_TCK); //显示运行时间 system(\); 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

sort(item,item+n,comparison); //实现单位重量的平均价值的物品的排序

for(i=0;i

float c=m;

for(i=0;ic) break; tem[i]=1; c-=item[i].w; }

if(i

for(i=0;i