当前位置: 首页 > news >正文

贪心算法及其简单习题

算法不能得到整体最优解,其最终结果却是最优解的很好近似。

1.活动安排问题:

    设有n个活动的集合E={1,2,,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,si <fi 。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说,当si≥fjsj≥fi时,活动i与活动j相容。

  例:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:

i

1

2

3

4

5

6

7

8

9

10

11

S[i]

1

3

0

5

3

5

6

8

8

2

12

f[i]

4

5

6

7

8

9

10

11

12

13

14

 

public class 活动安排问题 {
    public static int greedySelector(int [] s,int [] f,boolean a[])
    {
        int m=s.length;//长度
        a[1]=true;//默认第一个执行
        int count=1;//初始化为1
        int j=1;
        for (int i=2;i<m;i++)
        {
            if (s[i]>=f[j])//下一个事件的开始时间与下一个时间的结束时间作比较
            {//满足的话
                a[i]=true;//标记
                j=i;//重新赋值
                count++;//次数相加
            }
            else
            {
                a[i]=false;//不满足的话
            }
        }
        return count;
    }
    public static void main(String[] args) {
        int s[]={-1,1,3,0,5,3,5,6,8,8,2,12};
        int f[]={-1,4,5,6,7,8,9,10,11,12,13,14};
        boolean a[]=new boolean[s.length];
        System.out.println(greedySelector(s,f,a));
        for(int i=1;i<a.length;i++) {
            if(a[i]) {

                System.out.println(i+"开始"+s[i]+"结束"+f[i]);
            }
        }

    }
}

输出结果:

2.0-1背包问题:

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

 在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i

 

import java.util.Arrays;

public class 背包问题 {
    public static void main(String[] args) {
        int MAX_WEIGHT=150;//最大重量
        int[] weights = new int[]{35,30,60,50,40,10,25};//重量
        int[] values = new int[]{10,40,30,50,35,40,30};//价值
        GoGreedyPackage(MAX_WEIGHT, weights, values);
    }

    private static void GoGreedyPackage(int max_weight, int[] weights, int[] values) {
        int n=weights.length;
        double [] value=new double[n];//性价比数组
        int [] index=new int[n];//索引数组
        for (int i=0;i<n;i++)
        {
            value[i]=(double)values[i] /weights[i];
            index[i]=i;
        }

        for (int i=0;i<n-1;i++)//冒泡排序处理性价比数组,索引数组
        {
            for (int j=i+1;j<n;j++)
            {
                if (value[i]<value[j])
                {
                    double temp=value[i];
                    value[i]=value[j];
                    value[j]=temp;
                    int t=index[i];
                    index[i]=index[j];
                    index[j]=t;
                }
            }
        }
        索引是保存性价比排序的下标
        System.out.println("性价比排序"+Arrays.toString(value));
        int [] valuelast=new int[n];//性价比排序后的价值排序
        int [] weightlast=new int[n];//性价比排序后重量数组
        for (int i=0;i<n;i++)
        {
            valuelast[i]=values[index[i]];
            weightlast[i]=weights[index[i]];//按最佳性价比重新排序
        }
        System.out.println(Arrays.toString(weightlast));
        //int x[]=new int[n];//是否
        int maxval=0;//总价值
        int max=max_weight;//剩余重量
        for (int i=0;i<n;i++)
        {
            if (weightlast[i]<max)
            {
                //x[i]=1;
                max-=weightlast[i];
                maxval+=valuelast[i];
            }

        }
       // System.out.println(Arrays.toString(x));
        System.out.println(maxval);
        System.out.println(max);
    }
}

结果:

 这里没保存ID不好分辨,自己推一边应该没问题

3.多机调度:

多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

  这个问题是NP完全问题,到目前为止还没有有效的解法。对于这一类问题,贪心选择策略有时可以设计出较好的近似算法。


import java.util.*;

public class 多机调度 {
    public static class jobNode implements Comparable{//实现了一个比较的接口
        int id;
        int time;
        public jobNode(int id, int time) {//构造方法
            this.id = id;
            this.time = time;
        }
        @Override
        public int compareTo(Object o) {//重写比较函数,时间多的放前面
            int times=((jobNode)o).time;
            if (times<this.time)
            {
                return  -1;//时间少的排前面
            }
            else if (times==this.time)
            {
                return 0;
            }
            else return 1;
        }
    }
    public static class MachineNode implements Comparable//与上面一样
    {
        int id;
        int ava;

        public MachineNode(int id, int ava) {
            this.id = id;
            this.ava = ava;
        }

        @Override
        public int compareTo(Object o) {//工作时间时间少的排前面
            int times=((MachineNode)o).ava;
            if (times<ava)
            {
                return 1;
            }
            else if (times==ava) {
                return 0;
            }
            else
            {
                return -1;
            }
        }
    }
    public static int greed( int [] n,int a) {
        int P = n.length - 1;//记录长度
        int sum = 0;//记录时间
        if (P < a) {//加入任务数量少于机器数量的情况
            for (int i = 0; i < n.length - 1; i++) {
                sum += n[i];
            }
            return sum;
        } else {//任务多于机器数
            List<jobNode> jb = new ArrayList<jobNode>();//造一个jobnode链表保存
            for (int i = 0; i < P; i++) {
                jobNode T = new jobNode(i + 1, n[i + 1]);
                jb.add(T);
            }
            Collections.sort(jb);//调用系统的排序,时间多的放前面

            LinkedList<MachineNode> MN = new LinkedList<>();
            for (int i = 1; i <=a; i++) {
                MachineNode M = new MachineNode(i , 0);
                MN.add(M);
            }
            for (int i = 0; i < P; i++) {
                Collections.sort(MN);//持续按时间排序
                MachineNode mc = MN.peek();//取出机器
                mc.ava += jb.get(i).time;//累计时间
                sum = mc.ava;
            }
            return sum;
        }

    }

    public static void main(String[] args) {
        int[] a={0,2,14,4,16,6,5,3};
        int m=3;
        int sum=greed(a,m);
        System.out.println("时间用了"+sum);
    }
}

结果:

 

相关文章:

  • java特殊数据结构:栈Stack
  • 基于APB与I2C的多主多从架构设计
  • Visual Studio Code 自动编译 TypeScript
  • 【智能合约】——智能合约安全指南
  • 三、git分支操作
  • 猿创征文|Python基础——Visual Studio版本——pytest
  • 第二十四篇:稳定性之多环境建设
  • 【RHCE-第三天作业】
  • elementUI时间选择器:TypeError: value.getHours is not a function
  • “蔚来杯“2022牛客暑期多校训练营5
  • MyBatis Plus (七) --------- 插件扩展
  • css基础总结(css简介、css语法框架、css样式表格式、css选择器)
  • 东芝推出第三代碳化硅MOSFET来提高工业设备效率
  • Zookeeper集群搭建
  • 基于SSM的校园运动会管理系统
  • 【个人向】《HTTP图解》阅后小结
  • 2019年如何成为全栈工程师?
  • CSS进阶篇--用CSS开启硬件加速来提高网站性能
  • Fastjson的基本使用方法大全
  • idea + plantuml 画流程图
  • input的行数自动增减
  • iOS | NSProxy
  • Java 11 发布计划来了,已确定 3个 新特性!!
  • JavaScript 基础知识 - 入门篇(一)
  • JavaScript标准库系列——Math对象和Date对象(二)
  • Java面向对象及其三大特征
  • JS学习笔记——闭包
  • PAT A1092
  • React-redux的原理以及使用
  • Spark in action on Kubernetes - Playground搭建与架构浅析
  • Vue 动态创建 component
  • 机器学习 vs. 深度学习
  • 如何使用 OAuth 2.0 将 LinkedIn 集成入 iOS 应用
  • 如何选择开源的机器学习框架?
  • 使用 5W1H 写出高可读的 Git Commit Message
  • 腾讯优测优分享 | 你是否体验过Android手机插入耳机后仍外放的尴尬?
  • 运行时添加log4j2的appender
  • 怎样选择前端框架
  • ​力扣解法汇总946-验证栈序列
  • #、%和$符号在OGNL表达式中经常出现
  • (2)STL算法之元素计数
  • (51单片机)第五章-A/D和D/A工作原理-A/D
  • (done) NLP “bag-of-words“ 方法 (带有二元分类和多元分类两个例子)词袋模型、BoW
  • (附源码)SSM环卫人员管理平台 计算机毕设36412
  • (排序详解之 堆排序)
  • (十六)串口UART
  • (十五)Flask覆写wsgi_app函数实现自定义中间件
  • (中等) HDU 4370 0 or 1,建模+Dijkstra。
  • (转)memcache、redis缓存
  • ***linux下安装xampp,XAMPP目录结构(阿里云安装xampp)
  • **PHP二维数组遍历时同时赋值
  • *2 echo、printf、mkdir命令的应用
  • .bat批处理出现中文乱码的情况
  • .equals()到底是什么意思?
  • .halo勒索病毒解密方法|勒索病毒解决|勒索病毒恢复|数据库修复