您的位置:首页 > 健康 > 美食 > 软件项目管理论文_手机网站优化排名首页_网络营销优化推广_北京seo代理公司

软件项目管理论文_手机网站优化排名首页_网络营销优化推广_北京seo代理公司

2024/10/31 21:22:48 来源:https://blog.csdn.net/Day_and_Night_2017/article/details/143252389  浏览:    关键词:软件项目管理论文_手机网站优化排名首页_网络营销优化推广_北京seo代理公司
软件项目管理论文_手机网站优化排名首页_网络营销优化推广_北京seo代理公司

上文说到,贪心算法基于当前的现状,找到最优的选择进行决策。

这个问题其实就是个性价比的问题,性能就是价值val,价格就是重量wgt,这里不能称为价格了,应该叫代价。 

那么,如果我们每次选择的时候,都尽可能使用性价比最高的那个物品,是不是就可以找到最佳的选择了?

这里的性价比,就是 val / wgt

当然,因为可以选择方案中的物品的一部分,实际价值 = 单位价值 * wgt

我们把每个物品的性价比计算一下,排个序,是不是就能看出来哪个物品性价比最高?那么剩下的策略就是每次优先选择性价比最高的那个。

/* 物品 */
class Item {int w; // 物品重量int v; // 物品价值public Item(int w, int v) {this.w = w;this.v = v;}
}/* 分数背包:贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {// 创建物品列表,包含两个属性:重量、价值Item[] items = new Item[wgt.length];for (int i = 0; i < wgt.length; i++) {items[i] = new Item(wgt[i], val[i]);}// 按照单位价值 item.v / item.w 从高到低进行排序Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));// 循环贪心选择double res = 0;for (Item item : items) {if (item.w <= cap) {// 若剩余容量充足,则将当前物品整个装进背包res += item.v;cap -= item.w;} else {// 若剩余容量不足,则将当前物品的一部分装进背包res += (double) item.v / item.w * cap;// 已无剩余容量,因此跳出循环break;}}return res;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com