做一个信息发布网站要多少钱,设计之家效果图,网站建设中幻灯片如何加链接,做网站的图片分类作者 | 小灰来源 | 程序员小灰————— 第二天 —————————————————. . . . . . . .我们回到刚才的题目当中#xff0c;假设背包的容量是10#xff0c;有5个商品可供选择#xff0c;每个商品的价值和重量如图所示#xff1a;让我们来计算一下每件物品的… 作者 | 小灰来源 | 程序员小灰————— 第二天 —————————————————. . . . . . . .我们回到刚才的题目当中假设背包的容量是10有5个商品可供选择每个商品的价值和重量如图所示让我们来计算一下每件物品的性价比其结果如下毫无疑问此时性价比最高的是物品4我们把物品4放入背包当中背包剩余的容量是8我们选择物品1放入背包背包剩余的容量是4于是我们选择0.8份的物品5放入背包背包剩余的容量为0public static void main(String[] args) {int capacity 10;int[] weights {4,6,3,2,5};int[] values {9,3,1,6,5};System.out.println(背包最大价值 getHighestValue(capacity, weights, values));}public static double getHighestValue(int capacity, int[] weights,int[] values){//创建物品列表并按照性价比倒序ListItem itemList new ArrayList();for(int i0;iweights.length;i){itemList.add(new Item(weights[i], values[i]));}itemList itemList.stream().sorted(Comparator.comparing(Item::getRatio).reversed()).collect(Collectors.toList());//背包剩余容量int restCapacity capacity;//当前背包物品的最大价值double highestValue 0;//按照性价比从高到低选择物品for(Item item : itemList){if(item.weight restCapacity){highestValue item.value;restCapacity - item.weight;}else{//背包装不下完整物品时选择该件物品的一部分highestValue (double)restCapacity/(double)item.weight * item.value;break;}}return highestValue;}static class Item {private int weight;private int value;//物品的性价比private double ratio;public Item (int weight, int value){this.weight weight;this.value value;this.ratio (double)value / (double)weight;}public double getRatio() {return ratio;}}在这段代码当中我们借助了静态内部类Item从而更方便地记录性价比、获取重量和价值信息、按性价比排序。仍然给定一个容量是10的背包有如下三个物品可供选择这一次我们有个条件限制只允许选择整个物品不能选择物品的一部分。如果按照贪心算法的思路首先选择的是性价比最高的物品1那么背包剩余容量是4再也装不下其他物品而此时的总价值是6但这样的选择真的能让总价值最大化吗如果我们不选择物品1选择物品2和物品3的话剩余容量是0总价值是7显然76依靠贪心算法得出的结果未必是全局最优解。往期推荐阿里云投入 20 亿发力操作系统移动云API大赛决赛大奖花落谁家Redis很厉害使用规范来啦阿里云发布首颗云芯片倚天710点分享点收藏点点赞点在看
