没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全Unity3D教程：游戏开发算法（三）2

Unity3D教程：游戏开发算法（三）2

unity

需积分: 0 0 下载量 193 浏览量 2022-08-08 19:49:57 上传评论收藏 99KB DOCX 举报

温馨提示

试读

35页

Unity3D教程：游戏开发算法（三）2

资源详情

资源评论

资源推荐

Unity3D 教程：游戏开发算法（三）

Posted on 2013 年 06 月 26 日 by U3d / Unity3D 基础教程/被围观 60 次

六、贪婪法

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得

到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常

以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

例如平时购物找钱时，为使找回的零钱的硬币数最少，不考虑找零钱的所有各种发表

方案，而是从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，

当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种

方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面

值分别为 1、5 和 11 单位的硬币，而希望找回总额为 15 单位的硬币。按贪婪算法，应找

1 个 11 单位面值的硬币和 4 个 1 单位面值的硬币，共找回 5 个硬币。但最优的解应是 3

个 5 单位面值的硬币。

【问题】装箱问题

问题描述：装箱问题可简述如下：设有编号为 0、1、…、n-1 的 n 种物品，体积分别

为 v0、v1、…、vn-1。将这 n 种物品装到容量都为 V 的若干箱子里。约定这 n 种物品的

体积均不超过 V，即对于 0≤i＜n，有 0＜vi≤V。不同的装箱方案所需要的箱子数目可能不

同。装箱问题要求使装尽这 n 种物品的箱子数要少。

若考察将 n 种物品的集合分划成 n 个或小于 n 个物品的所有子集，最优解就可以找

到。但所有可能划分的总数太大。对适当大的 n，找出所有可能的划分要花费的时间是无

法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放

到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。

不失一般性，设 n 件物品的体积是按从大到小排好序的，即有 v0≥v1≥…≥vn-1。如不满

足上述要求，只要先对这 n 件物品按它们的体积从大到小排序，然后按排序结果对物品重

新编号即可。装箱算法简单描述如下：

　　{ 输入箱子的容积；

　　输入物品种数 n；

　　按体积从大到小顺序，输入各物品的体积；

　　预置已用箱子链为空；

　　预置已用箱子计数器 box_count 为 0；

　　for (i=0;i　　 { 从已用的第一只箱子开始顺序寻找能放入物品 i 的箱子 j；

　　if （已用箱子都不能再放物品 i）

　　{ 另用一个箱子，并将物品 i 放入该箱子；

　　box_count++；

　　}

　　else

　　将物品 i 放入箱子 j；

　　}

上述算法能求出需要的箱子数 box_count，并能求出各箱子所装物品。下面的例子说

明该算法不一定能找到最优解，设有 6 种物品，它们的体积分别为： 60、45、35、20、

20 和 20 单位体积，箱子的容积为 100 个单位体积。按上述算法计算，需三只箱子，各箱

子所装物品分别为：第一只箱子装物品 1、 3；第二只箱子装物品 2、4、5；第三只箱子

装物品 6。而最优解为两只箱子，分别装物品 1、4、5 和 2、3、6。

若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩

余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按

以上算法编写的程序。

【程序】

001

# include

002

003

　　# include

004

005

　　typedef struct ele

006

007

　　{ int vno;

008

009

　　struct ele *link;

010

011

　　} ELE;

012

013

　　typedef struct hnode

014

015

　　{ int remainder;

016

017

　　ELE *head;

018

019

　　Struct hnode *next;

020

021

　　} HNODE;

022

023

　　void main()

024

025

　　{ int n, i, box_count, box_volume, *a;

026

027

　　HNODE *box_h, *box_t, *j;

028

029

　　ELE *p, *q;

030

031

　　Printf(“输入箱子容积\n”);

032

033

　　Scanf(“%d”,&box_volume);

034

035

　　Printf(“输入物品种数\n”);

036

037

　　Scanf(“%d”,&n);

038

039

　　A=(int *)malloc(sizeof(int)*n);

040

041

　　Printf(“请按体积从大到小顺序输入各物品的体积：”);

042

043

　　For (i=0;i　　 Box_h=box_t=NULL;

044

045

　　Box_count=0;

046

047

　　For (i=0;i　　 { p=(ELE *)malloc(sizeof(ELE));

048

049

　　p->vno=i;

050

051

　　for (j=box_h;j!=NULL;j=j->next)

052

053

　　if (j->remainder>=a[i]) break;

054

055

　　if (j==NULL)

056

057

　　{ j=(HNODE *)malloc(sizeof(HNODE));

058

059

　　j->remainder=box_volume-a[i];

060

061

　　j->head=NULL;

062

063

　　if (box_h==NULL) box_h=box_t=j;

064

065

　　else box_t=boix_t->next=j;

066

067

　　j->next=NULL;

068

069

　　box_count++;

070

071

　　}

072

073

　　else j->remainder-=a[i];

074

075

　　for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);

076

077

　　if (q==NULL)

078

079

　　{ p->link=j->head;

080

081

　　j->head=p;

082

083

　　}

084

085

　　else

086

087

　　{ p->link=NULL;

088

089

　　q->link=p;

090

091

　　}

092

093

　　}

094

095

　　printf(“共使用了%d 只箱子”，box_count);

096

097

　　printf(“各箱子装物品情况如下：”);

098

099

　　for (j=box_h,i=1;j!=NULL;j=j->next,i++)

100

101

　　{ printf(“第%2d 只箱子，还剩余容积%4d，所装物品有；\n”,I,j->remainder);

102

103

　　for (p=j->head;p!=NULL;p=p->link)

104

105

　　printf(“%4d”,p->vno+1);

106

107

　　printf(“\n”);

108

109

　　}

110

111

　　}

112

【问题】马的遍历

问题描述：在 8×8 方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘

每一格并且只经过一次的一条路径。

马在某个方格，可以在一步内到达的不同位置最多有 8 个，如图所示。如用二维数组

board[ ][ ]表示棋盘，其元素记录马经过该位置时的步骤号。另对马的 8 种可能走法（称

为着法）设定一个顺序，如当前位置在棋盘的（i，j）方格，下一个可能的位置依次为

（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-1）、（i-1，j-

2）、（i+1，j-2）、（i+2，j-1），实际可以走的位置尽限于还未走过的和不越出边界

剩余34页未读，继续阅读

寻路算法：一种可视化工具，用于AI和游戏开发中使用的核心搜索算法。特别感谢Amit Patel及其出色的教程，它们为我提供了灵感。 #MadeWithUnity

搜索算法可视化。灵感来自深度优先搜索呼吸优先搜索统一成本搜索（Dijkstra算法的特例）最佳优先搜索 A *搜索（稳定优先级队列实现）欧氏距离启发式：曼哈顿距离启发式：

World Map Strategy Kit 2 V9.7.1

5星 · 资源好评率100%

World Map Strategy Kit 2是功能强大的游戏工具包，可用于基于真实或虚构的世界地图创建策略游戏。包括出色的视觉吸引力功能，这些功能实施起来很复杂，可以为您开发游戏提供AAA级启动。 ***视觉功能*** - 标准/...

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

5星 · 资源好评率100%

ISO 27001:2022英文版 ISO 27001:2022中文版(本人译稿，再也不改了版) ISO 27002:2022英文版 ISO 27002:2022中文版(本人译稿，再也不改了版) 全部为文字版PDF文件，带完整目录标签。

Goby红队版-win-x64-2.4.7版本

Goby红队专版:集成1500个poc和exp ，覆盖普通版本所有功能，开箱即用使用方式: 解压后双击goby.exe运行即可注意事项: 最新的漏洞不可以在线更新，可自行添加poc和exp 重要的事情说三遍不要用于非法或未授权测试！不要用于非法或未授权测试！不要用于非法或未授权测试！自行判断可刑性！

Chrome Header Editor 插件

Chrome Header Editor 插件及配置文件，旨在取消因流量异常或IP异常导致的谷歌人机验证。

ISO SAE 21434-2021 中文版.pdf

4星 · 用户满意度95%

ISO SAE 21434中文版

安全认证cisp教材全套

5星 · 资源好评率100%

cisp教材全套，最全的CISP电子版教材，总共20章节分20个PDF文件

OpenVAS GVM 中文翻译补丁

自己制作的粗糙版放入/usr/share/gvm/gsad/web/locales目录刷新浏览器即可

2024最新：Hvv中常见的面试问题

国护网常见的面试问题，十年国护经验总结，帮助你通关国护网面试。

评论收藏

内容反馈

練心

粉丝: 24
资源: 305

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

Unity3D教程：游戏开发算法（三）2

评论0

最新资源

Unity3D教程：游戏开发算法（三）2

评论0

Unity3D教程：游戏开发算法

Unity3D 游戏开发教程

Unity3D游戏开发教程

Unity3D 游戏开发

Unity3D教程：游戏开发算法（二）2

Unity3D教程：游戏开发算法（一）2

Unity3D 2018 最新最全800个脚本教程

Unity3D 实战视频教程 保卫萝卜 2D 游戏开发

Unity3D游戏开发

基于Unity3D多平台网络斗地主的设计与实现毕业设计.doc

Unity3d游戏图形学从理论到实战精讲

2018 猎豹网校 教程大全 资源难找赶紧保存吧

GeneticSharp：GeneticSharp是一个快速，可扩展，多平台和多线程的C＃遗传算法库，可简化使用遗传算法（GA）进行的应用程序开发

寻路算法：一种可视化工具，用于AI和游戏开发中使用的核心搜索算法。 特别感谢Amit Patel及其出色的教程，它们为我提供了灵感。 #MadeWithUnity

World Map Strategy Kit 2 V9.7.1

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

安全认证cisp教材全套

OpenVAS GVM 中文翻译补丁

2024最新：Hvv中常见的面试问题

最新资源

Unity3D 实战视频教程保卫萝卜 2D 游戏开发

2018 猎豹网校教程大全资源难找赶紧保存吧

寻路算法：一种可视化工具，用于AI和游戏开发中使用的核心搜索算法。特别感谢Amit Patel及其出色的教程，它们为我提供了灵感。 #MadeWithUnity