• 【算法设计与分析】贪心法

    目录

    一、实验目的

    1. 掌握贪心法的基本思想

    2. 掌握相关问题的贪心算法

    3. 验证、巩固和补充课堂讲授的理论知识。

    二、实验内容

    (1) 背包问题

    (2) 带时限的作业排序问题

    三、实验结果及分析

    1.算法设计

    2.思路分析

    3.核心代码

    4.测试样例设计

    5.运行结果（截图）

    6.难点分析

    7.算法时间复杂度分析

    四、总结

    一、实验目的

    1. 掌握贪心法的基本思想

            基本思想：贪心算法首先设计某种贪心选择策略，第一步做出当前状态的最优选择；然后问题会被演化与原问题相同但是规模更小的子问题；最后用相同的贪心选择策略求解子问题。

    2. 掌握相关问题的贪心算法

            (1) 背包问题

            (2) 带时限的作业排序问题

    3. 验证、巩固和补充课堂讲授的理论知识。

    二、实验内容

    (1) 背包问题

            已知一个载重为M的背包和n件物品，第i件物品的重量为wi。如果将第i件物品的全部装入背包，收益为pi，其中wi>0, pi>0, 0<=i

    (2) 带时限的作业排序问题

            设有⼀个单机系统、⽆其它资源限制且每个作业运⾏相等时间，假定每个作业运⾏1个单位时间。现有n(00，di为整数，1<=i<=n。如果作业能够在截⽌期限之内完成，可获得pi>0的收益。问题要求得到⼀种作业调度⽅案，该⽅案给出作业的⼀个⼦集和该作业⼦集的⼀种排列，使得若按照这种排列次序调度作业运⾏，该⼦集中的每个作业都能如期完成，并且能够获得最⼤收益。

    三、实验结果及分析

            主要包括算法设计思路，详细设计、调试分析、运行结果以及算法的时间复杂度分析等。

    1.算法设计

    （1）背包问题

            根据每个物品的单位质量价格，优先放入当前剩余物品中单位质量价格最大的物品，直到将背包装满。

    （2）带时限的作业排序问题

            根据当前时钟的大小依次选取时限大于当前时钟且收益最大的作业执行。当若干作业的时限仅比当前时钟大一个单位时选取这些作业中收益最大的作业。当若干作业的时限远大于当前时钟则顺次执行这些作业。

    2.思路分析

    （1）背包问题

            Step 1在输入每个物品属性的同时计算每个物品的单位质量价值；

            Step 2将物品按照物品的单位质量价值从大到小排序；

            Step 3依次将当前剩余物品中单位质量价值最大物品最大限量地放入背包，并记录每件物品被装入了整件物品的多少部分，直到背包被装满。

    （2）带时限作业的排序问题

            Step 1将作业优先按照时限从小到大排序，时限相同则按照收益从大到小排序；

            Step 2依次访问作业数组，根据当前时钟判断可选取的作业；

            Step 3直到将作业数组完全访问一遍。

    3.核心代码

    （1）背包问题

    1. typedef struct asd{ //记录物品属性
    2.  
    3.     int id,price,weight;
    4.  
    5.     double valueperweight; //单位质量价值
    6.  
    7.     double put; //放入部分占总量的百分比
    8.  
    9. }sth;
    10.  
    11.  
    12.  
    13. int main(){ //背包问题贪心计算
    14.  
    15.     int M,num;
    16.  
    17.     int i,j;
    18.  
    19.     double value=0;
    20.  
    21.     sth goods[100];
    22.  
    23.     //输入背包总容量
    24.  
    25.     scanf("%d%d",&M,&num);
    26.  
    27.     //输入物品属性、计算单位质量价值
    28.  
    29.     for(i=0;i
    30.  
    31.         scanf("%d%d%d",&goods[i].id,&goods[i].price,&goods[i].weight);
    32.  
    33.         goods[i].valueperweight=(double)goods[i].price/(double)goods[i].weight;
    34.  
    35.     }
    36.  
    37.     //按照物品物品的单位质量价值从大到小排序
    38.  
    39.     sort(goods,num,0);
    40.  
    41.     i=0;
    42.  
    43.     //放入背包
    44.  
    45.     while(M>0){
    46.  
    47.         if(goods[i].weight<=M){
    48.  
    49.          //背包容量大于物品总量，放入全部
    50.  
    51.             goods[i].put=goods[i].weight/goods[i].weight;
    52.  
    53.             value+=goods[i].price;
    54.  
    55.             M-=goods[i].weight;
    56.  
    57.         }else if(goods[i].weight>M){
    58.  
    59.          //背包容量小于物品总量，放入部分
    60.  
    61.             goods[i].put=(double)M/goods[i].weight;
    62.  
    63.             value+=goods[i].valueperweight*M;
    64.  
    65.             M-=M;
    66.  
    67.         }
    68.  
    69.         i++;
    70.  
    71.     }
    72.  
    73.     //按照id排序，为输出做准备
    74.  
    75.     sort(goods,num,1);
    76.  
    77.     for(i=0;iprintf("%0.2f ",goods[i].put);
    78.  
    79.     printf("\n%0.2f",value);
    80.  
    81.     return 0;
    82.  
    83. }
    84.  
    85.  
    86.  
    87. void sort(sth a[],int n,int flag){ //排序函数
    88.  
    89.     int i,j;
    90.  
    91.     sth t;
    92.  
    93.     if(flag==0){
    94.  
    95.         for(i=1;i<=n-1;i++){
    96.  
    97.            for(j=1;j<=n-i;j++){
    98.  
    99.                if(a[j-1].valueperweight
    100.  
    101.                     t=a[j-1];a[j-1]=a[j];a[j]=t;
    102.  
    103.                }
    104.  
    105.              }
    106.  
    107.          }
    108.  
    109.     }
    110.  
    111.     else{
    112.  
    113.         for(i=1;i<=n-1;i++){
    114.  
    115.              for(j=1;j<=n-i;j++){
    116.  
    117.                    if(a[j-1].id>a[j].id){
    118.  
    119.                        t=a[j-1];a[j-1]=a[j];a[j]=t;
    120.  
    121.                    }
    122.  
    123.              }
    124.  
    125.         }
    126.  
    127.     }
    128.  
    129. }

    （2）带时限作业的排序问题

    1. //作业属性
    2.  
    3. typedef struct strct{
    4.  
    5.     int id,price,deadline;
    6.  
    7. }Job;
    8.  
    9.  
    10.  
    11. int main(){ //带时限作业的排序
    12.  
    13.     int i,j;
    14.  
    15.     int num,value,idcnt,time,id[100];
    16.  
    17.     Job job[100];
    18.  
    19.     scanf("%d",&num);
    20.  
    21.     //作业性质
    22.  
    23.     for(i=0;iscanf("%d%d%d",&job[i].id,&job[i].price,&job[i].deadline);
    24.  
    25.     //将作业优先按照时限从小到大排序，时限相同则按照收益从大到小排序
    26.  
    27. sort(job,num);
    28.  
    29.     i=0;j=0;value=0;idcnt=0;time=0;
    30.  
    31.     while(i
    32.  
    33.      //执行作业
    34.  
    35.         if(job[i].deadline>time){
    36.  
    37.             id[j++]=job[i].id;
    38.  
    39.             value+=job[i].price;
    40.  
    41.             i++;
    42.  
    43.             //时钟后移
    44.  
    45.             time++;
    46.  
    47.         }else
    48.  
    49. //当前作业时限小于当前时钟，说明当前作业不被执行；
    50.  
    51. //即时钟不变，选取后续作业
    52.  
    53. i++;
    54.  
    55.     }
    56.  
    57.     //按照作业id排序，方便输出
    58.  
    59.     array_sort(id,j);
    60.  
    61.     for(i=0;iprintf("%d ",id[i]);
    62.  
    63.     printf("\n%d",value);
    64.  
    65.     return 0;
    66.  
    67. }
    68.  
    69.  
    70.  
    71. //排序
    72.  
    73. void sort(Job a[],int n){
    74.  
    75.     int i,j;
    76.  
    77.     Job t;
    78.  
    79.     for(i=1;i<=n-1;i++){
    80.  
    81.       for(j=1;j<=n-i;j++){
    82.  
    83.         if(a[j-1].deadline>a[j].deadline){
    84.  
    85.           t=a[j-1];a[j-1]=a[j];a[j]=t;
    86.  
    87.         }else if(a[j-1].deadline==a[j].deadline){
    88.  
    89.           if(a[j-1].price
    90.  
    91.             t=a[j-1];a[j-1]=a[j];a[j]=t;
    92.  
    93.           }
    94.  
    95.         }
    96.  
    97.       }
    98.  
    99.     }
    100.  
    101. }
    102.  
    103. void array_sort(int a[],int n){
    104.  
    105.     int i,j;
    106.  
    107.     int t;
    108.  
    109.     for(i=1;i<=n-1;i++){
    110.  
    111.       for(j=1;j<=n-i;j++){
    112.  
    113.         if(a[j-1]>a[j]){
    114.  
    115.           t=a[j-1];a[j-1]=a[j];a[j]=t;
    116.  
    117.         }
    118.  
    119.       }
    120.  
    121.     }
    122.  
    123. }

    4.测试样例设计

    （1）背包问题：

            测试样例1

    输入

    20 3

    0 25 18

    1 24 15

    2 15 10

    输出

    0.00 1.00 0.50

    31.50

            测试样例2

    输入

    30 5

    0 25 18

    1 24 15

    2 15 10

    3 10 10

    4 36 5

    输出

    0.00 1.00 1.00 0.00 1.00

    75.00

    （2）带时限作业的排序问题：

            测试样例1

    输入

    4

    1 100 2

    2 10 1

    3 15 2

    4 27 1

    输出

    1 4

    127

            测试样例2

    输入

    7

    1 99 2

    2 6 1

    3 16 2

    4 27 1

    5 12 5

    6 11 5

    7 10 4

    输出

    1 4 5 6 7

    159

    5.运行结果（截图）

    （1）背包问题

    （2）待时限作业的排序问题

    6.难点分析

    （1）Point1:

            在时限背包问题的过程中，因为物品的属性值中全部都是整数型（int），但是单位质量价值和放入部分的占比均为小数（double），故在计算过程中多次出现计算值被写入成“0.0”的情况。

    （2）Point2:

            在第一版本的代码中未引入时钟，导致存在“时限远大于时钟，但作业未被执行（时限相同的作业只执行了一个）”的情况。

    7.算法时间复杂度分析

    （1）背包问题

            main()函数中向背包中放入物品，时间复杂度为O(n)。

            void sort(sth a[],int n,int flag)采用冒泡排序的方式，时间复杂度为O(n2)。

    （2）带时限作业的排序问题

            main()函数中向执行作业，时间复杂度为O(n)。

            void sort(Job a[],int n)和void array_sort(int a[],int n)采用冒泡排序方式，时间复杂度为O(n2)。

    四、总结

            通过此次的实验，对贪心法的算法思想有了更深的了解。也就是不断选取当前状态的最优解，由一系列局部最优解得到全局最优解。同时也发现并不是所有问题都可以通过贪心算法求得最优解，因为使用贪心算法之前需要明确贪心选择策略。

  • 相关阅读:
    Windows环境下Hadoop的安装和配置
    Hadoop3：MapReduce的序列化和反序列化
    STC 51单片机44——实现0.5秒间隔的单向流水灯
    特征工程建模可解释包（note）
    删除的照片怎么找回？教你5个好方法快速恢复
    拼多多面试题
    记录级别索引：Hudi 针对大型数据集的超快索引
    Netty深入浅出（无处不在的IO）
    算法模型总结：前后指针法
    软件系统建模&架构风格-架构论文（三十八）
  • 原文地址：https://blog.csdn.net/weixin_52099756/article/details/140102569