Base TSP

问题描述

已知图G=(V,E),利用贪心策略求解图G上的从顶点1出发的最短巡回旅行路线,要求输出找到的(近似)最短巡回旅行路线。

要求:给出问题的贪心算法,并编程实现

阅读全文
活动安排问题

问题描述

设有n个活动的集合e={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

阅读全文
最长公共子序列

问题描述

给定两个字符串,求其最大公共子序列

问题分析

本题是典型的动态规划问题,我们将大字符串分解成小字符串进行计算。

阅读全文
苹果树剪枝

问题描述

有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个孩子的结点)。这棵树共有n个结点(叶子点或者树枝分叉点),编号为1~n,树根编号一定是1。

阅读全文
背包一维数组实现

背包分类

0-1背包

只用考虑物品放与不放

阅读全文
背包问题

问题描述

已知n种物品的体积、价值和数量,背包的容积为C,从物品中选择装入背包的物品,每种物品装入数量不超过物品的数量,请设计算法求出装入价值最大的装法。

阅读全文
寻找中项和第k小元素

问题描述

在统计学领域中,中项是一个非常关键的常用的指标值。序列的中项是指排好序后序列的“中间”元素,中项是指序列的第[n/2]个最小元素。寻找序列中项的问题被称为中项值问题,寻找序列中第k小元素的问题被称为选择问题。

阅读全文
大整数乘法

题目描述

程序设计语言中的整型数据类型可以存放一定范围内的整数,超出这个范围的大整数就不能再用普通变量存储和操作,这样的整数通常被称为“大整数”。大整数的存储需要借助于数组或链表等,其操作也需要编写程序完成。

阅读全文
冒泡排序

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

阅读全文
旋转数组

题目描述

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

阅读全文
Algolia