背包问题贪心法.doc

背包问题贪心法
实验报告
学院：计算机科学与技术学院
班级：****
学号：****
姓名：****
一、实验目的
1）以背包问题为例，掌握贪心法的基本设计策ndif
X(i) 1
cucu-W(i)
repeat
if i≤n then X(i) cu/W(i)
endif
end GREEDY-KNAPSACK
三、程序流程图
以策略三为例：（此时物品已经按物品价值与重量比值p/w降序排列）
物品i
W(i)>cu
X(i) 1
cucu-W(i)
X(i) 1
cucu-W(i)
i++
i<n
退出循环
i≤n
程序结束
X(i)cu/W(i)
四、以策略三为例程序清单
#include <>
#include <>
struct good
{
double v,w; //权值及重量
double x; //解向量
};
void cpygood(good a,good b){
= ;
= ;
= ;
}
void insertionsort(good *goods, int n){
int i,j;
good item;
for(j=1;j<n;j++){
//cpygood(item, goods[j]);
= goods[j].v;
= goods[j].w;
= goods[j].x;
i = j-1;
while( > goods[i].v/goods[i].w && i>=0)
{
//cpygood(goods[i+1], goods[i]);
goods[i+1].v = goods[i].v;
goods[i+1].w = goods[i].w;
goods[i+1].x = goods[i].x;
i--;
}
//cpygood(goods[i+1],item);
goods[i+1].v = ;
goods[i+1].w = ;
goods[i+1].x = ;
}
}
void greedy(int n, double c, good *goods)
{ //n为物品数量，c为背包能承受的重量
double m = c;
int i;
insertionsort(goods,n);
for(i=0;i<n;i++)
goods[i].x = 0;
for(i=0;i<n;i++){
if(goods[i].w > m)
break;
goods[i].x = 1;
m -= goods[i].w;
}
if(i < n)
goods[i].x = m/goods