Banch_limit_Tsp

问题描述

设有n个城市,城市之间道路的长度均大于或等于0,还可能是∞(对应城市之间无交通线路)。一个旅行商从某个城市出发,要经过每个城市一次且仅一次,最后回到出发的城市,问他如何走才能使他走的路线最短?

要求:优先使用矩阵归约确定限界函数的方法,或者其他方法实现。

阅读全文
Banch_limit_0-1pacage

问题描述

0-1背包问题

已知n个物品的价值vi和重量wi,背包的载重W,求能放入背包的最大价值。用分支限界方法解决此问题

阅读全文
temp

问题描述

邮票问题

设有已知面额的邮票m种,每种有n张,问用总数不超过n张的邮票进行组合,能组合的邮票面额中可以连续的面额数最多有多少?

阅读全文
color

问题描述

3-着色问题

判定无向图G=(V,E)是否可以用3种颜色着色,可以,请给出着色方案。

阅读全文
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,从物品中选择装入背包的物品,每种物品装入数量不超过物品的数量,请设计算法求出装入价值最大的装法。

阅读全文
Algolia