贪心算法与分数背包
上文说到,贪心算法基于当前的现状,找到最优的选择进行决策。
这个问题其实就是个性价比的问题,性能就是价值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;
}
原文地址:https://blog.csdn.net/Day_and_Night_2017/article/details/143252389
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/376151.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/376151.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!