Hanovertown-CSDN博客

原创回溯法-装载问题

子集树问题和子集树的0-1背包问题类似，但是没有考虑价格#include #include #include using namespace std;//第五章装载问题templateclass Loading{ friend Type MaxLoading(Type [],Type,int,int[]); // private: public:

2016-11-26 14:15:07 4028

原创最优服务次序问题-贪心算法

1、最优服务次序问题（1）问题描述：　　设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1（2）编程任务：　　对于给定的n个顾客需要的服务时间，编程计算最优服务次序。（3）数据输入：　　第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。（4）结果输出:　　计算出的最小平均等待时间。（5）输入示例10

2016-11-26 13:47:34 13858

原创活动安排问题-贪心算法

在时间段内选择尽可能多的活动（0~14）#include #include #include #include using namespace std;//struct Extent{ int a,b;} A[10002];/*1 412 142 133 50 68 128 115 73 86 105 9测试数据，n=11;*/b

2016-11-26 13:38:38 1308

原创符号三角形问题-回溯法

貌似是子集树问题问题描述：　　由14个“+”号和14个“-”号组成的符号三角形。　　2个同号下面是“+”号，2个异号下面是“-”号。在一般情况下，符号三角形第一行有N个符号，该问题要求对于给定n计算有多少种不同的符号三角形。使其所含的+ — 个数相同。算法设计：　　1 x[i] =1 时，符号三角形的第一行的第i个符号为+　

2016-11-26 13:07:25 2691

原创图的m着色问题-回溯法

排列树问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?输出结果：#include using namespace std;const int N=5; //const int M=3;//5.8节图的m着色问题（回溯法）/*0 1 1 1 01 0

2016-11-25 21:39:14 4908

原创旅行售货员问题-回溯法

排列树问题问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。输出结果： // 旅行员售货问题回溯法求解 #include using namespace std; const int N = 4;//

2016-11-25 21:23:11 3503

原创棋盘覆盖问题-递归分治

#include #include using namespace std; int Board[20][20]; int tile=1;void ChessBoard(int tr,int tc,int dr,int dc,int size){ if(size==1) return; int t =tile++; int s=size/2;

2016-11-25 20:48:29 647

原创合并排序-非递归

#include //合并排序非递归--自然合并排序typedef int Type;using namespace std;void Merge(Type c[],Type d[],int l,int m,int r){ //合并c[l:m] c[m+1:r] 到 d[l:r] int i=l,j=m+1,k=l;

2016-11-25 20:42:04 822

原创合并排序-递归分治

按我的想法，简单地说，合并排序的思路就是：先递归，后排序。#includeusing namespace std;void merge_sort(int a[],int p,int r);void merge(int a[],int p,int q,int r);int b[20];int main(){ int a[11]={1,49,60,12,-12,101,1

2016-11-25 20:37:14 592

原创快速排序-递归与分治

#include using namespace std;int partition(int data[],int lo,int hi) //双向扫描。{ int key=data[lo]; //以第一个元素为主元 int l=lo; int h=hi; while(l<h) { while(key<=data[h] && l<h) h--; data[l

2016-11-25 19:45:25 432

转载最长公共子序列问题（c++）-动态规划

文章转载自http://www.cnblogs.com/xudong-bupt/archive/2013/03/15/2959039.html笔者使用的是c++代码。众所周知，用到两个重要的数组。一）flag[ ][ ] 标志图中小标走向；二）num[ ][ ] 存储中间结果，也就是上图的内容。两个数组均采用全局变量的声明方式。省去传参的过（ma）程（fan）！！！

2016-11-21 16:16:33 776

动态规划法经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。【问题】求两字符序列的最长公共字符子序列问题描述：字符序列的子序列是指从给

2016-11-21 16:02:08 742

原创最长公共子序列（未完...）动态规划&递归

代码因为c++水平限制，主要是数组初始化或传参的问题。运行控制台程序出错。。先放在这里，日后改动。会转载两篇最长公共子序列的文章，我的代码是借鉴java实现的哪一篇的（数组）传参；c++的那一篇应用了全局变量，从

2016-11-21 15:53:55 544

原创 0-1背包问题使用回溯法

对于0-1 背包问题可以用动态规划算法解决，这里先不说这种方法。只介绍回溯法，0-1背包问题的回溯法解决的解空间是子集树。下面给出最简洁的代码，比较方便理解呢#include #includeusing namespace std;int n,c,bestp;//物品的个数，背包的容量，最大价值int p[10000], //物品的价值

2016-11-20 20:49:44 2447

原创回溯法排列树-最佳调度（最短时间完成）

宝宝怀着无比激动的心情写下这篇文章，，因为本人实在太菜了。C++里类的成员函数在类外面定义时忘记加上 "类名"+" : : "了。。。。。。问题描述:假设有n个任务由k个可并行工作的机器完成。完成任务i 需要的时为Ti 。试设计一个算法找出完成这n个任务的最佳调度,使完成全部任务的时间最早。算法设计:对于给定的整数n和k，以及完成任务i需要的时间Ti ,i=1~n。计算完成

2016-11-19 16:03:56 1873

原创递归分治-求集合最大元

问题描述在规模为n的数据元素集合中找出最大元。当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。当n>2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。先分别找出各自组中的最大元，然后将两个最大元进行比较，就可得n个元素的最大元。代码#include using namespace std;int max(int a

2016-11-14 14:33:11 1164

原创无向图的深度优先遍历和广度优先遍历（递归）

无向图的深度优先遍历和广度优先遍历（递归） queue.h源代码注释：包括队列数据类型的定义和相关操作（出队，入队，判断队空，判断队列中是否存在某元素） int searchQ(LinkQueue &Q,int s) 函数的作用：在将邻接顶点放入队列之前需要先判断队列中是否已存在此元素，通过查找避免队列中有重复元素。 #i

2016-05-23 20:43:01 14455

原创链式线性表的就地逆置

#include #include #include 采用单链表就地逆置的思想大概是这样： 1.断开单链表的头结点与第一个节点，这样头结点就变成了一个新的空链表； 2.然后从第一个结点开始，每次都取下原有链表的一个结点，插入到新链表表头(注意是从第一个结点开始，并不是第二个结点开始^-^)； 3.然后到最后一个结点，就完事了。循环为:

2016-03-27 11:45:32 1635

转载用链式线性表实现两个一元多项式相加

#include #include #include using namespace std;typedef struct PolyNode {int coef;int exp;PolyNode *next;}node;node * CreatPoly(){ PolyNode *h,*tail,*s; int coef,exp; h=( Pol

2016-03-26 16:38:19 5000 1

原创链式线性表的操作

//链式线性表的创建，查找，删除，插入，合并操作#include #include #include using namespace std;typedef struct LNode{ int data; struct LNode *next;}LNode,*LinkList;void CreatList(LinkList &L,int n){ L=(LinkList) malloc(sizeo

2016-03-25 21:19:31 460

原创二分

#include #include #include using namespace std;int erfenF(int data[],int t,int nn){ int l,r,m; l=0; r=nn-1; while(r>=l) { m=(l+r)/2; if(t==data[m])

2015-04-12 12:42:37 377

认真你就输了