鱼C论坛

 找回密码
 立即注册
分享 算法设计13 --背包问题
2018-12-22 12:27
有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。 限制条件 1 = n =100 1 = wi,vi = 100 1 =W =10000
个人分类: 算法|271 次阅读|0 个评论
分享 算法设计12 --Fence Repair
2018-12-21 13:55
农夫约翰为了修理栅栏,要将一块很长的木板切割成N块。准备切成的木板的长度为L1、L2、...、Ln,未切割前木板的长度恰好为切割木板长度的总和。每次切断木板时,需要的开销为这块木板的长度。例如长度为21的木板要切成长度为5,8,8的三块木板。长度为21的木板切成长为13和8的板时,开销为21。再将长度为13的板切成长度为5 ...
个人分类: 算法|290 次阅读|0 个评论
分享 算法设计11 --Saruman's Army
2018-12-21 12:59
直线上有N个点。点i的位置是Xi。从这N个点中选择若干个,给它们加上标记。对每一个点,其距离为R以内的区域里必须有带有标记的点(自己本身带有标记的点,可以认为与其距离为0的地方有一个带有标记的点)。在满足这个条件的情况下,希望能为尽可能少的点添加标记。请问至少要有多少点被加上标记? 限制条件 1 = N ...
个人分类: 算法|282 次阅读|0 个评论
分享 算法设计10 --Best Cow Line
2018-12-20 16:11
给定长度为N的字符串S,要构造一个长度为N的字符串T。起初,T是一个空串,随后反复进行下列任意操作。 从S的头部删除一个字符,加到T的尾部 从S的尾部删除一个字符,加到T的尾部 目标是要构造字典序尽可能小的字符串T。 示例操作: S = "CDB" 开头:S = "DB" T = "ABCC" T = "ABC" 末尾: S ...
个人分类: 算法|316 次阅读|0 个评论
分享 算法设计9 --区间调度问题
2018-12-19 10:48
有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参加与否。如果选择了参与,那么自始至中都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始的瞬间和结束的瞬间也是不允许的)。 限制条件 1 = N = 100000 1 = si =ti =10^9
个人分类: 算法|251 次阅读|0 个评论
分享 算法设计8 --硬币问题
2018-12-19 09:51
有1元,5元,10元,50元,100元,500元的硬币各C1,C5,C10,C50,C100,C500枚。现在要用这些硬币来支付A元,最少需要多少枚硬币?假定本题至少存在一种支付方案。 限定条件 0 = C1,C5,C10,C50,C100,C500 = 10^9 0 = A = 10^9
个人分类: 算法|273 次阅读|0 个评论
分享 算法设计7 --迷宫最短路径
2018-12-18 16:21
给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出起点到终点所需的最小步数。请注意,本题假定从起点一定可以移动到终点。 限制条件 N,M = 100
个人分类: 算法|206 次阅读|0 个评论
分享 算法设计6 --Lake Counting
2018-12-18 10:37
有一个大小为N*M的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?(八连通指的是下面图中相对W的*的部分) *** *W* *** 限制条件 N,M=100
个人分类: 算法|157 次阅读|0 个评论
分享 算法设计5 --部分和问题
2018-12-18 09:41
给定整数a1,a2,...,an,判断是否可以从中选出若干数,使它们的和恰为k。 限制条件 1 =n =20 -10^8 = ai =10^8 -10^8 = k =10^8
183 次阅读|0 个评论
分享 算法设计4 --难度增加的抽签问题
2018-12-18 09:14
如果将最开始的抽签问题中关于n的限制条件改为1=n=1000,那么应该如何呢?最初的四重循环算法是O(n^4)时间的,将n=1000带入n^4得到10^12.
个人分类: 算法|169 次阅读|0 个评论
12下一页

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 20:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部