背包入门 背包笔记大部分内容参考来自这篇文章[1]和wiki上的内容[2]。 01背包问题 题目:有N件物品和一个容量为V的背包。第i件物品的费用是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 这是最基础的背包问题,后面的背包问题都由01背包问题衍生。问题的特点是:每种物品仅有一件,只能选择放或不放。 如果这个问题采用枚举的思想,他的时间复杂度 2022-07-16
Floyd算法入门 所有顶点对间的最短路径问题(Floyd算法)Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。简称Floyed(弗洛伊德)算法,是最简单的最短路径算法,可以计算图中任意两点间的最短路径。 Floyd的时间复杂度是$O (N^3)$,适用于出现负边权的情况。 算法的基本思想:开始时,以任意两个顶点之间的有向边的权值作为路径长度,没有有向边时,路径长度为∞以后 2022-05-16 #算法