AcWing 2. 01背包问题 状态表示 $f(i, j)$ 表示体积 j 的情况下 装下前 i 个物品的最优解 状态计算 $f(i , j) = max(f(i - 1, j), f(i - 1, j - v(i)) + w(i))$ $f(i - 1, j)$表示不选第 i 个物品的最大价值 $f(i - 1, j - v(i)) + w(i)$ 表...

视频教学资料

AcWing 842. 排列数字 本题用的算法思想为回溯法 排列数字1，2，3的解空间树： 可行解共有6种 顺序图解： 1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;const int N ...

AcWing 826. 单链表 e[i]: 存放需要存入的值 ne[i]：存放下一个节点的下标 idx :记录当前的操作的位置 插入头结点 利用一个head指针记录头结点的位置 1234void add_to_head(int x){ e[idx] = x, ne[idx] = head, head = idx ++ ;} 插入操...

AcWing 785. 快速排序 快速排序本质上是分治法 分解成子问题 递归处理子问题 合并子问题 1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>using namespace std;const int N = 1e...

题目源自某高校C++的OJ 将做过的C++ OJ题目整理合并了一下，总共有一百多道题目，手动合并自然是不可能的 这个时候我们就可以使用shell脚本来取代这种机械化的重复劳动了，由于写成博客需要使用Markdown文档，我们就结合md文档的语法来编写这个merge.sh脚本吧 1vim merge.sh 脚本内容： 123456789101112#!/us...

一、实验目的： 掌握最大流算法思想。 学会用最大流算法求解应用问题。 二、内容： 有m篇论文和n个评审，每篇论文需要安排a个评审，每个评审最多评b篇论文。请设计一个论文分配方案。 要求应用最大流解决上述问题，画出m=10，n=3的流网络图并解释说明流网络图与论文评审问题的关系。 编程实现所设计算法，计算a和b取不同值情况下的分配方案，如果没有...

一、实验目的： 掌握图的连通性。 掌握并查集的基本原理和应用。 二、内容： 1. 桥的定义 在图论中，一条边被称为“桥”代表这条边一旦被删除，这张图的连通块数量会增加。等价地说，一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。 图 1 没有桥的无向连通图 图 2 这是有16个顶点和6个桥的图（桥以红色线段标示） 2. 求解问题 找...

一、实验目的： 掌握动态规划算法设计思想。 掌握流水线问题的动态规划解法。 二、内容： 汽车厂有两条流水线，每条流水线有n个处理环节（station）: S1,1，…，S1,n 和 S2,1，…，S2,n，其中下标的第一个字母表示流水线编号（流水线1和流水线2）。其中S1, j 和 S2, j 完成相同的功能，但是花费的时间不同，分别是a1, j , a...

一、实验目的： 掌握回溯法算法设计思想。 掌握地图填色问题的回溯法解法。 二、内容： 背景知识： 为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。 我们可能还想使用尽可能少的不同颜色进行填涂。一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。 每张地图包含四个相互连接的国家时，它们至少需要四...

一．实验目的 对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。 要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。 要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。 分别对N=100,1000,10000,100000，统计算法运行时间，比较理...

题目源自某高校数据结构的OJ 郑重声明 代码仅供参考，请勿直接抄袭，~(嗯，我自己学的时候也抄了好多)~本文字数过多，请善用Ctrl + F进行检索 DS–图非0面积: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051...