花枫不是殇~-CSDN博客

原创 Rabin-Karp算法和KMP算法

#pragma once#ifndef HANDLE_STRING_H_#define HANDLE_STRING_H_#include<string>using std::string;namespace _secret{ void build(const string& p, int* next); bool check_vaule(const string& t, const string& p,int index); void Count_val

2021-08-13 21:44:19 284

原创线性规划之单纯形法

没学概率论，于是跳过了随机化算法。但是单纯形法折腾了半天发现是运筹学的知识，于是乎又找了视频自学了运筹学的相关知识。韩信带净化，原理实在没法去深入研究。只知道怎么用即可。LinearProgram.h#pragma once#ifndef LINEARPROGRAM_H_#define LINEARPROGRAM_H_//请先将问题转换成约束标准型线性规划问题class LinearProgram{private: int row;//决定有多少个约束方程 int col;//决定有多少

2021-08-09 21:58:44 221

原创迷宫BFS

#include<iostream>#include<queue>#include<iomanip>using namespace std;struct Point{ int x; int y;};//点坐标const int height = 10;//迷宫的高const int width = 10;//迷宫的宽const int maze[height][width] = { {1,1,0,1,1,1,0,1,0,0}, {0,1,1,1,

2021-08-07 12:08:03 90

原创算m点问题

#include<iostream>#include<vector>#include<iomanip>using namespace std;enum { WHITE, GRAY };enum { PLUS = 1, MINUS, MULTIPLY, DIVIDE };vector<double> a = { 7,2,2,12,3 };vector<int> Color;const int k = (int)a.size();co

2021-08-05 18:31:12 248

原创子集和问题

#include<iostream>#include<iomanip>using namespace std;#define WHITE 0#define GRAY 1const int n = 5;const int S[n] = { 2,2,6,5,4 };int Color[n]{ WHITE };//选中情况,WHITE表示未选中int c = 10;int Count = 0;void Subsum(int index=0,int sum = 0);v

2021-08-04 12:05:56 60

原创图的m着色问题

#include<iostream>#include<iomanip>using namespace std;const int n = 5;const int m = 4;int sum = 0;const int Graph[n][n] = { {0,1,1,1,0}, {1,0,1,1,1}, {1,1,0,1,0}, {1,1,1,0,1}, {0,1,0,1,0}};int Color[n] = { 0 };//0是未着色状态bool check

2021-08-04 00:16:20 62

原创最大团问题

因为完全子图和最大团之间存在包含关系，所以可以只搜索比当前顶点序号大的邻接点，从而避免重复。#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>using namespace std;const int N = 111; //设置矩阵的大小int graph[N][N]; //用邻接矩阵存储图boo

2021-08-03 19:29:24 148

原创符号三角问题

终于到了我最熟悉的回溯法了#include<iostream>using namespace std;int sum=0;//记录答案总个数。const int n = 7;//第一行一共有多少个符号，n>=2int triangular_matrix[n][n]{0};//存储符号(+用1表示，-用-1表示)void solve(int floor,int Count);void dispose(int index,int Count);//处理第一行int main()

2021-08-02 17:25:22 60

原创最优分解问题

/** 设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，* 且使这些自然数的乘积最大。* * 看到这个问题，不由得想到小学的一道题，将一根长n的木条拆成四份，使得这四根木条可以拼成* 长方形，并问怎样拆分使得面积最大。* 很自然的想到，每根n/4，拼成正方形面积最大。* 证明：假设正方形边长为a，则s1=a^2。现在相对的两条边分别增加和减少b，* 则s2=(a-b)(a+b)=a^2-b^2<s1。* 随着b越大，s2会越小。* 因此在分解数的时候注意分解后相邻

2021-08-01 17:35:14 130

原创多元Huffman编码问题

/** 在一个操场的四周摆放着n堆石子。现在要将石子有次序地合并成一堆。* 规定每次至少选两堆，最多选k堆石子合并成新的一堆，合并的费用为新的一堆石子数。* 对于给定的n堆石子，计算合并成一堆的最大费用和最小费用。* * 假设有a,b,c,d,e五堆石子已经按升序排好，*（为方便描述，这里设任意小的任意堆合并不会比后面的大，任意大的合并不会比前面小）。* 最多一次可以合并三堆，最少一次两堆。* 一次三堆:1、 a b c d e cost=0* 2、 a+b+c d e

2021-08-01 11:49:39 377

原创最优合并问题

还是优先队列#include<iostream>#include<vector>#include<queue>using namespace std;vector<int>a = { 5,12,11,2 };int maxtimes, mintimes = 0;int main(){ priority_queue<int, vector<int>, greater<int>> q1; priority_q

2021-07-31 23:43:13 53

原创模拟Huffman编码

#pragma once#ifndef HUFFMAN_H_#define HUFFMAN_H_#include<string>#include<queue>#include<set>#include<map>#include<vector>#include<algorithm>#include<iostream>using namespace std;template<typename Type

2021-07-31 18:03:44 66

原创多机调度问题

#include<iostream>#include<vector>#include<set>#include<iomanip>#include<algorithm>using namespace std;/** 这里有必要解释的是为什么要把独立作业的时间按照降序排序，而不是升序。* 为了方便说明，我们假设机器可以刚好处理完这些作业。（否则就难以说明降序排序也是最优解的了）* 如果是升序排序，越往后选择，任务的耗时会越大，* 最

2021-07-31 00:15:05 192

原创图像压缩动态规划

对图形学不了解，看到这个题目挺懵的/** 首先，要知道：像素点存储的位数（bit）=log2(像素点的个数)+1。1<=像素点的个数<=255。其中log(像素点的个数)向下取整* 例:将像素序列表示成数组p[n]={10,9,12,40,50,35,15,12,8,10,9,15,11,130,160,240}。* 像素点存储的最大位数=log2(255)+1=8。（优先选取最大的位数为其他像素点个数存储的基准）* 因此可以选择都用8bit存储，这样一共消耗16*8=128bit的空

2021-07-29 11:40:47 310

原创 PolandBall and Gifts

比较复杂/** 有n个人，第i个人想送给第p[i]个人一份礼物。* p是一个排列，且p[i]≠i。* 很遗憾现在有k个人忘记带礼物了。如果i忘带礼物了，* 那么i和p[i]都不会收到礼物。* 问无法收到礼物的人最多和最少有几个。* k<=n<=10^6* * 例1：* n=5,k=2,p[n]={3,4,1,5,2}。* 最少有2个，最多有4个。* * 例2：* n=10,k=1,p[n]={2,3,4,5,6,7,8,9,10,1}。* 最少有2个，最多有2个。

2021-07-20 16:27:37 81

原创 Coins

/** 有n种面额的硬币。第i个硬币的面额是v[i]，个数为c[i]。* 问最多能搭配出多少种不超过m的金额。* 1<=n<=100，1<=m<=100000，1<=v[i]<=100000,1<=c[i]<=1000* 例：* n=3,m=10,v[n]={1,2,4},c[n]={2,1,1}。* 答案是8。* 设f[i][j]表示考虑到第i种硬币，金额为j的最大搭配方案。1<=i<=n,1<=j<=m* 1、i=1

2021-07-19 18:01:19 118

原创多重背包问题的常规算法和二进制拆分法

/** 有N件物品和一个容量为V的背包。* 第i件物品的体积是c[i]，价值是w[i]。* 第i件物品最多有a[i]个可用。* 求将那些物品装入背包可以使得价值总和最大。*/#include<iostream>#include<vector>#include<iomanip>#include<queue>using namespace std;#define choice 1class thing{private: int vol

2021-07-18 21:44:56 114

原创动态规划求解Fire问题

这个问题其实用贪心策略更好吧，硬要用动态规划也是没有问题的。/** 现在一个房子里着火了，你需要从这个房里抢救一些东西出来。* 有n件物品，第i件物品的价值是p[i]，抢救需要花费t[i]的时间，* 如果物品超过d[i]的时间还没有被抢救出来就会被烧掉。* 问能救出的物品价值之和最大为多少，并且输出你能抢到的物品编号。* 这个问题看起来和活动选择问题很像，区别是这个问题的起始时间都是0。* 设f[i][j]表示考虑到第i个物品，到j时刻为止最大能救的价值量。* 如果不选择物品，则f[i][j

2021-07-18 21:42:17 76

原创最小逆序对数

基础不扎实，写得时候被"f[i] = new int[K + 1];“这行代码坑了半天，写成"f[i] = new int[K + 1]{INT_MAX};”，还没有反应过来，哈哈。。。/** 有一个长度为n的序列，每个数都是1~K中的整数。* 现在有一些位置的数被遮住了，用-1表示。* 你可以往这些位置填1~K中的数，使得整个序列的逆序对数最小，* 求最小的逆序对数。* N<=10000,K<=100* 逆序对数：i<j，a[i]>a[j]。（有关逆序对数的性质及相关

2021-07-15 19:56:44 537

原创关于搬寝室问题自己的看法

自学算法有一个月，动态规划是真的难，本来有点想放弃，不过最近边打游戏边学习，动态规划有了一点眉目。本人一个小菜鸟，研究这个搬寝室问题研究了一下午，总算弄懂了。/** 有n个行李，每个行李有一个重量。* 现在你要搬走2k个行李，你一共去k次。每次左手右手各* 拿一个行李，假设这两个行李的重量分别是x和y。* 那么这一次搬运产生的疲惫度是(x-y)^2* 现在你希望最小化疲惫度* 2<=2k<=n<2000*/#include<iomanip>#include&

2021-07-14 19:51:20 101

原创随便弄的图邻接表存储以及相关的基础算法

自学了一下图的算法，想自己封装一个图，但期末考试耽搁了，没有弄完，一考完立刻抢修,虽然有些不如人意…用的是C++和部分C的APIpicture.h#pragma once#ifndef PICTURE_H_#define PICTURE_H_#define WHITE 0#define GRAY 1#include<vector>/*无权图*/class picture{private: /*邻接表*/ typedef struct adjacent { cha

2021-07-08 11:11:30 152

原创哈希表处理冲突的线性探测法与拉链法

线性探测法/******关键码为非负数*******/#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>#define NULLKEY -32768#pragma warning (disable:4805)typedef struct HashTable{ int elem; //元素存放处 int count; //当前元

2021-02-12 00:08:54 406

原创 c语言实现图的邻接表

居然成功了，我的天~~#include<stdio.h>#include<stdlib.h>#include<stdlib.h>#define OFF 0//未被访问#define ON 1//已经被访问#define MAXSIZE 100//队列最大长度#pragma warning (disable:4996)typedef struct { int base[MAXSIZE];//存放结点的下标 int front;//头指针，若队列不空，指向

2021-02-04 22:35:21 147

原创赫夫曼树构造及其带权长度计算

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;#pragma warning (disable:4996)#define OFF 0//权值未被使用#define ON 1//权值已被使用typedef struct HTNode { unsigned int weight;//为ss数组初始化方便，规定

2021-02-03 13:30:13 175

原创链式队列模拟

用链表的形式好处就是没有空间不够用或者空间剩余太多的问题#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct Line { int data;//数据域 struct Line* next;//指针域}Line;Line* createLine()//创建队列（队头）{ Line* front; if ((front = (Line*)malloc(sizeof(Lin

2021-01-27 11:51:08 60

原创不采用结构体，简单模拟一下顺序栈和顺序队列

顺序栈表的模拟#include<stdio.h>#include<string.h>#include<stdlib.h>#define Zero 0//元素为空的标识int main(){ int* Data;//创建栈表 int choice,i,Maxsize; printf("请输入栈表最大长度:"); scanf_s("%d", &Maxsize); if ((Data = (int*)malloc(Maxsize * sizeof(int))) ==

2021-01-26 18:36:43 119

m0_52386243的博客