贪心算法在货船装箱中的应用

目录

贪心算法简介

货船装箱问题

问题描述:

设计思想:

具体算法描述:

算法证明

贪心法求解问题具有的性质:

数学归纳法证明贪心选择性质:

反证法证明最优子结构性质:

总结


前面的内容是一些介绍与分析,对于有基础的朋友可以直接跳过,跳转到代码和算法证明。

个人觉得,贪心主要难在证明hh

贪心算法简介

       贪心算法总是作出当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的是在某种量度标准上的局部最优解。在使用贪心算法设计求解的过程中选择能产生问题最优解的最优量度标准是一个核心问题。

       对于一个给定的问题,往往可能有好几种量度标准这些量度标准初看似乎都是可取的。选出最优量度标准并不是一件容易的事不过一旦选出某个问题的最优量度标准,那么用贪心算法求解这个问题就特别有效。贪心算法的基本思路是从问题的某个初始解出发,逐步逼近给定的目标,以尽可能快地求得更好的解。当到达算法中的某一步不能再继续前进的时候算法停止。

实现该算法的过程如下:

货船装箱问题

 问题描述:

       有一艘船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样,但货箱的重量各不相同。设第i个货箱的重量为w[i]而货船的最大载重量为c我们的目的是在体积不受限制的货船上装入最多的货物。

该问题可以形式化描述为:


其中,变量x[i]=0表示i个货箱不装入货船,x[i]=1表示装入货船。

(1)式是目标函数,(2)式是约束条件。

满足约束条件的任一集合(x[1]…, x[n])是一个可行解(即能装下),使目标函数取最大值的可行解是最优解

 设计思想:

        船可以分步装载每步装一个货箱且需要考虑装载哪一个货箱根据这种思想可利用如下贪婪原则:从剩下的货箱中,选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小,从而可以装载更多的货箱。根据这种策略,首先选择最轻的货箱,然后选择次轻的货箱,如此下去直到所有的货箱均装上货船或者货船上不能再容纳其它任何一个货箱,即不能超出最大载重量


      假设有8个货箱 n=8每个货箱的重量分别是w[1,2,…,n]=[150,200,50,30,70,90,100,80],货船的总装载重量是c=400。利用贪心算法时,所要考察货箱的顺序为4,3,5,8,6,7,1,2。而货箱4,3,5,8,6的总重量为32030+50+70+80+90)个单位且已被装载,剩下的装载能力为80个单位,小于剩下的任何一个货箱。在这种贪心算法解决当中得到[x[1],x[2],…,x[n]]=[0,0,1,1,1,1,0,1],∑x[i]=5(1≤i≤8),简而言之,选择了34568号货箱,共5个。

 具体算法描述:

#include <iostream>
#include <algorithm>
#include <utility> 
using namespace std;

const int N = 100; // 假设货箱数量不超过100
int n, c;
int w[N]; 
int x[N] = { 0 }; //0表示不选择,1表示选择

int main() {
   
    cin >> n >> c;
    pair<int, int> a[N]; // 用于记录原始索引和重量的pair

    for (int i = 0; i < n; i++) {
        cin >> w[i];
        a[i] = make_pair(w[i], i + 1); 
    }

    // 按照货箱重量从小到大排序
    sort(a, a + n);

    int sum = 0;// 已经装载的货箱总重量
    int count = 0;//已装载的货箱数量

    for (int i = 0; i < n; i++) {
        int weight = a[i].first;
        int index = a[i].second; 

        // 如果加上当前货箱的重量没有超过货船的最大载重量
        if (sum + weight <= c) {
            x[index - 1] = 1; // 选择这个货箱
            sum += weight; // 更新已装载的货箱总重量
            count++;
        }
    }

    cout << "共装载" << count << "个货箱:";
    for (int i = 0; i < n; i++) 
        if (x[i] == 1) cout << i + 1<<' ';

    cout << "\n重量分别是:";
    for (int i = 0; i < n; i++)
        if (x[i] == 1) cout << w[i] << ' ';

    return 0;
}

算法证明

 贪心法求解问题具有的性质:

贪心选择性质贪心选择,在每一步选择中,我们都会做出在当前看来是最好的选择,这个选择依赖于之前所做的选择,但不依赖于未来的选择。在货船装箱问题的贪心算法中,我们按照货箱重量的升序进行选择,每一步都选择当前可以装载的最小重量的货箱。

最优子结构性质最优子结构性质是指一个问题的最优解包含其子问题的最优解。对于货船装箱问题,如果一个问题的最优解存在,则它的最优子集也存在最优解,并且问题的最优解可以通过组合子问题的最优解来构造。

 数学归纳法证明贪心选择性质:

特殊情况:当没有剩余的货箱需要装载时(即count=n时,所有的货箱都已经被装载)

其余情况:

       归纳假设:假设对于所有重量不超过 C 的货箱集合,贪心算法能够找到最优解。

       归纳步骤:考虑一个重量为 C + x(其中 x>0)的货箱集合。我们的目标是证明贪心算法也能找到这个集合的最优解。

证明:

1. 根据归纳假设,首先从所有重量不超过 C 的货箱中选择一个最优子集。这个子集的总重量不超过 C ,并且是最优的,因        为它是上一阶段根据贪心算法选择的。
2. 现在考虑是否加入一个新的货箱,其重量为 x

       如果这个新货箱被装载,那么它将替换掉原来子集中的一个或多个货箱,因为需要保持总重量不超过 W + x。由于贪心算法总是选择最小的重量,这个新货箱的加入将使得总重量增加,但不会增加到超过 W + x

       如果这个新货箱不被装载,那么保持原来的最优子集不变,因为它已经是在不超过 C 的条件下的最优解。

 最后,在这两种情况下,都得到了一个在不超过 W + x 条件下的最优解。这就证明了,即使加入了新的重量为 x的货箱,贪心算法仍然能够找到最优解。

 反证法证明最优子结构性质:

        假设:这个问题的最优解 S 不包含其子问题的最优解。也就是说,存在一个子集  S,它是S 的一部分,但 S 不是其子集问题的最优解。 

         由于  S不是其子集问题的最优解,那么必然存在另一个解 S′′使得 S′ ′S的子集问题的最优解,并且 S′′S 更优或者至少同样优。 如果将 S′ ′替换 S中的相应子集,将得到一个新的解 S′′′由于 S′′是一个更优或者同样优的解, S′′′也将是一个更优或者同样优的解。  通过这种方式,可以逐步替换 S中的所有子集,直到得到一个完全由最优子集解构成的解S~

        它显然优于或等于 S如果 S~优于 S,那么 S不能是最优解,可以推出 S~是问题的最优解;如果 S ′ ~S同样优,那么 S就不是唯一的最优解,因为 S~也是最优解。

        这与原假设相矛盾,货船装箱问题的最优解确实包含其子问题的最优解,这就证明了最优子结构性质。

总结

    时间复杂度分析:程序主要计算量在于将货箱依照其重量从小到大的顺序排序使用的是algorithm库中的sort函数对包含重量和索引的 pair 数组进行排序。在最坏情况下,排序的时间复杂度是 O(nlogn),其中 n 是货箱的数量。

    总的来说,贪心算法是一种有效的问题求解策略,尤其适用于那些可以分解为最优子结构的问题。然而它所做出的仅是在某种量度标准上的局部最优解,并非所有问题都可以用贪心算法来解决,且贪心算法并不总能保证得到全局最优解。

相关推荐

  1. 贪心算法应用

    2024-04-01 20:28:01       18 阅读
  2. 贪心算法魅力与应用

    2024-04-01 20:28:01       8 阅读
  3. Clickhouse货品标签场景应用

    2024-04-01 20:28:01       24 阅读
  4. 遗传算法及其稀疏阵列应用

    2024-04-01 20:28:01       22 阅读
  5. 机器学习算法数据挖掘应用

    2024-04-01 20:28:01       8 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-01 20:28:01       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-01 20:28:01       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-01 20:28:01       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-01 20:28:01       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-01 20:28:01       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-01 20:28:01       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-01 20:28:01       7 阅读

热门阅读

  1. 自定义多阶段倒计时实现分段倒计时

    2024-04-01 20:28:01       4 阅读
  2. 1364:二叉树遍历(flist)

    2024-04-01 20:28:01       4 阅读
  3. 利用ChatGPT打造精彩的学术论文写作体验

    2024-04-01 20:28:01       4 阅读
  4. 通过多选按钮选择需要修改什么字段

    2024-04-01 20:28:01       5 阅读
  5. Qt:常见的exec()函数

    2024-04-01 20:28:01       6 阅读
  6. React组件异常捕获的解决思路

    2024-04-01 20:28:01       5 阅读
  7. HTML元信息

    2024-04-01 20:28:01       4 阅读
  8. 配置一个nginx的server, 提供获取ip的服务

    2024-04-01 20:28:01       4 阅读
  9. 标题:AI大模型学习:解放智能的未来之路

    2024-04-01 20:28:01       5 阅读