Java排序算法之贪心算法

        

        贪心算法是一种优化问题的解决方法,它在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最优的。贪心算法常用于最优化问题,比如最小生成树、哈夫曼编码、最短路径等。贪心算法是一种简单而有效的算法,它不需要对问题的所有情况进行全局搜索,可以在较短时间内得到较优解。但是,由于贪心算法仅考虑局部最优解,可能导致无法得到全局最优解。因此,在使用贪心算法时需要对问题进行分析,判断贪心策略是否可行。

        贪心算法是一种常见的算法思想,特点是每次决策选择当前状态下最优的解,而不考虑未来可能的影响。在实际应用中,贪心算法通常用于求解最优化问题,比如背包问题、最短路径问题、任务调度问题等。

下面是一个简单的Java实现,以求解背包问题为例:

public class GreedyAlgorithm {

    /**
     * 背包问题,贪心算法实现
     * @param weights 物品重量
     * @param values 物品价值
     * @param capacity 背包容量
     * @return 最大价值
     */
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        // 将物品按照单位价值从大到小排序
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i], i);
        }
        Arrays.sort(items, (a, b) -> {
            return b.valuePerWeight - a.valuePerWeight;
        });

        int maxVal = 0;
        int curCap = capacity;
        // 依次选择单位价值高的物品,直至背包装满
        for (int i = 0; i < n && curCap > 0; i++) {
            int idx = items[i].idx;
            int w = weights[idx];
            int v = values[idx];
            if (w <= curCap) {
                maxVal += v;
                curCap -= w;
            } else {
                maxVal += v * curCap / w;
                curCap = 0;
            }
        }
        return maxVal;
    }

    /**
     * 物品类
     */
    private static class Item {
        int weight;
        int value;
        int idx;
        int valuePerWeight;

        public Item(int weight, int value, int idx) {
            this.weight = weight;
            this.value = value;
            this.idx = idx;
            this.valuePerWeight = value / weight;
        }
    }
}

在这个实现中,我们首先将所有物品按照单位价值从大到小排序,然后依次选择单位价值高的物品,直至背包装满。这个算法的时间复杂度为$O(n\log n)$,其中$n$为物品的数量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/151161.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java排序算法之希尔排序

希尔排序&#xff08;Shell Sort&#xff09;又称“缩小增量排序”&#xff0c;是直接插入排序算法的一种更高效的改进版本。它的基本思想是&#xff1a;首先将整个数组按照一定的间隔分成若干个子序列&#xff0c;然后对每个子序列分别进行插入排序&#xff0c;减小间隔&#…

day28_JQuery

今日内容 零、 复习昨日 一、正则表达式 二、JQuery 零、 复习昨日 js已经学完,js是让页面动态变化 1) 基本语法(变量,运算,逻辑,函数) 2) 事件(给标签绑定不同的事件) 3) dom(改变标签内容,属性,样式)一、引言 1.1 jQuery概述 原生js获得dom对象: var obj document.getElem…

李宏毅机器学习入门笔记——第三节

Convolutional Neural Network&#xff08;CNN&#xff09; 卷积神经网络 padding表示超过图片矩阵的距离 stride表示步长 常见的卷积都是3*3&#xff0c;同时可以知道图片的组成就是rgb也就是三个矩阵组成 使用卷积就是共用参数&#xff0c;减少参数量&#xff0c;不需要看整张…

Opengauss到Oracle增量同步, 使用debezium

一、概述 PG到Oracle的同步方案使用debezium kafka kafka-connect-jdbc。debezium是一款开源的变更捕获软件&#xff0c;它以kafka的connector形式运行&#xff0c;可以捕获PostgreSQL、MySQL、Oracle中的变更数据&#xff0c;保存到kafka。kafka-connect-jdbc是confluent公…

第一型曲面积分的第二型曲面积分的区别与联系【从几何知识的角度思考】

此处为曲线积分------>【问题思考总结】第一型曲线积分和第二型曲线积分的区别与联系【从几何知识的角度思考】 一二型曲面积分有什么区别&#xff1f;&#xff08;了解&#xff09; 一型曲面积分&#xff1a; 由dS进行表示。可以想像&#xff0c;dS是一个面积微元&#x…

MySQL数据库清理Relay_Log_File日志

背景 “Relay_Log_File” 是 MySQL 中用于复制的参数之一。在 MySQL 复制中&#xff0c;当一个服务器作为主服务器&#xff08;master&#xff09;时&#xff0c;它会将其更改写入二进制日志文件&#xff08;binary log file&#xff09;。而另一个服务器作为从服务器&#xf…

阿里云99元VS腾讯云88元,双11云服务器价格战,谁胜谁负?

在2023年的双十一优惠活动中&#xff0c;阿里云推出了一系列令人惊喜的优惠活动&#xff0c;其中包括99元一年的超值云服务器。本文将带您了解这些优惠活动的具体内容&#xff0c;以及与竞争对手腾讯云的价格对比&#xff0c;助您轻松选择最适合的云服务器。 99元一年服务器优…

每日汇评:积极的数据可能会推动澳元/美元的上涨

继 9 月份增加 6700 个就业岗位之后&#xff0c;澳大利亚 10 月份预计将增加 18000 个就业岗位&#xff1b; 失业率预计将从 3.6% 升至 3.7%&#xff0c;维持在历史低点附近&#xff1b; 澳元/美元在美元疲软的支撑下维持看涨基调&#xff0c; 其面临关键阻力位0.6520&#xff…

【Linux】初识网络

目录 背景 协议 什么是协议 协议分层 OSI七层模型 TCP/IP模型 网络协议栈与 OS 的关系 网络传输 局域网中直接通信 数据的封装与分用 局域网通信原理 数据碰撞 跨路由器进行远端通信 IP的介绍 传输演示 背景 &#x1f9ca;一开始&#xff0c;计算机都是一台台独…

Java实现拼图游戏

拼图游戏是一种智力类游戏&#xff0c;玩家需要将零散的拼图块按照一定的规律组合起来&#xff0c;最终拼成完整的图案。拼图游戏的难度可以根据拼图块数量、拼图的形状、图案的复杂程度等因素来调整。这种游戏适合各个年龄层的玩家&#xff0c;能够提高大脑的观察力、空间感知…

WPF xaml Command用法介绍

WPF (Windows Presentation Foundation) 中的命令设计模式是一种用于分离用户界面逻辑和业务逻辑的方法。在WPF中&#xff0c;这种模式通过命令接口&#xff08;如 ICommand&#xff09;实现&#xff0c;使得用户界面组件&#xff08;如按钮、菜单项等&#xff09;可以触发不直…

工厂自动化中DCS软件

概述 Monitor.Analog是新一代运行监控系统&#xff0c;是物联网时代数据驱动的智能工厂的神经中枢。通过连接到阿自倍尔专有的在线故障预测系统&#xff08;该系统利用 AI&#xff08;人工智能&#xff09;&#xff09;以及利用来自各个智能设备的监控和诊断数据的系统&#x…

Unity Meta Quest 一体机开发(六):HandGrabInteractor 和 HandGrabInteractable 知识点

文章目录 &#x1f4d5;教程说明&#x1f4d5;HandGrabInteractor⭐HandGrabAPI⭐HandWristPoint⭐GripPoint⭐PinchPoint⭐PinchArea⭐HandGrabVisual⭐HandGrabGlow &#x1f4d5;HandGrabInteractable⭐Support Grab Type⭐Pinch Grab Rules 和 Palm Grab Rules⭐Unselect M…

2023版Idea创建JavaWeb时,右键new没有Servlet快捷键选项

问题&#xff1a;右键时&#xff0c;没有创建servlet的快捷键&#xff0c;如下图&#xff1a; 解决方法&#xff1a; 1.打开idea&#xff0c;点击File>settings(设置)&#xff0c;进入settings页面&#xff0c;如下 从上图中的Files选项中没看到有servlet选项&#xff0c;…

拿到信创天翼云电脑账号后,我又傻眼了...

在《面向国产系统的 App 发布&#xff0c;含泪总结》中&#xff0c;我就吐槽过信创产品的不靠谱。用户购买一台终端&#xff0c;都没法用&#xff0c;得经历复杂的账号申请。 紧催慢催&#xff0c;等待了半个月之后&#xff0c;今天终于拿到了账号。然而&#xff0c;满怀期待登…

人工智能+游戏 会带来什么

“人工智能游戏” 写在前面 随着人类生活水平的日益提高&#xff0c;游戏正在为越来越多的人们带去欢乐。同时&#xff0c;作为21世纪新兴科学技术的人工智能&#xff0c;也正在研究人员的努力下不断向前突破。那么&#xff0c;这两列高速前进的“火车”能否接轨并行呢&#…

【数据结构】线段树(点修区查)

数据结构-线段树&#xff08;点修区查&#xff09; 前置知识 分治递归二叉树 思路 我们需要维护一个支持单点修改&#xff0c;区间查询的数据结构&#xff0c;并且要求在线&#xff0c;一般使用线段树解决。 线段树是一个二叉树形的数据结构。 线段树的思想很简单&#xff0c…

算法学习打卡day45|动态规划:股票问题总结

Leetcode股票问题总结篇 动态规划的股票问题一共六道题&#xff0c;买卖股票最佳时机和买卖股票手续费都是一个类型的问题&#xff0c;维护好买入和卖出两个状态即可&#xff0c;方法一摸一样。而冷冻期也差不多就是状态多了点&#xff0c;买入、保持卖出、当日卖出、以及冷冻期…

OpenGL_Learn12(光照)

续OpenGL_Learn11&#xff08;光照&#xff09;-CSDN博客 1. 镜面高光 和漫反射光照一样&#xff0c;镜面光照也决定于光的方向向量和物体的法向量&#xff0c;但是它也决定于观察方向&#xff0c;例如玩家是从什么方向看向这个片段的。镜面光照决定于表面的反射特性。 我们通…

IDEA没有Add Framework Support解决办法

点击File—>Settings 点击第一个设置快捷键 点击apply和ok即可 我们要点击一下项目&#xff0c;再按快捷键ctrlk 即可
最新文章