背包问题

mac2024-12-05  23

给定一个载重量为M的背包,考虑n个物品,其中第i个物品的重量 wi ,价值vi (1≤i≤n),要求把物品装满背包,且使背包内的物品价值最大。 如果物品可以分割,则称为背包问题(贪心算法)。

为方便计算,建立如下的数据结构,表示物品的参数: struct bag{ int w; //物品的重量 int v; //物品的价值 double c; //单位重量的价值,v/w }a[1001]; //存放物品的数组 排序因子(按性价比降序): bool cmp(bag a, bag b){ return a.c >= b.c; } 使用标准模板库函数排序: sort(a, a+n, cmp);

//形参n是物品的数量,c是背包的容量M,数组a是按物品的性价比降序排序 double knapsack(int n, bag a[], double c){   double cleft = c;        //背包的剩余容量   int i = 0;   double b = 0;       //背包内物品的总价值获得的价值   //当背包还能完全装入物品i   while(i<n && a[i].w<cleft)  {     cleft -= a[i].w;     b += a[i].v;     i++;   }   //装满背包的剩余空间   if (i<n) b += 1.0a[i].vcleft/a[i].w;   return b; } 如果要获得解向量 ,则需要在数据结构中加入物品编号: struct bag{ int w; int v; double c; //单位重量的价值,v/w double x; //装入背包的量,0≤x≤1 int index; //物品编号 }a[1001];

计算背包问题的贪心算法,同时得到解向量 double knapsack(int n, bag a[], double c){   double cleft = c;   int i = 0;   double b = 0;   while(i<n && a[i].w<=cleft)  {     cleft -= a[i].w;     b += a[i].v;      //物品原先的序号是a[i].index,全部装入背包     a[a[i].index].x = 1.0; //因为形参数组a已经排序     i++;   }   if (i<n) {     a[a[i].index].x = 1.0cleft/a[i].w;     b += a[a[i].index].xa[i].v;   }   return b; }

最新回复(0)