算法分析与设计实验报告--动态规划

1、算法分析与设计实验报告完成日期：20011.11.241、实验目的(1) 掌握动态规划方法贪心算法思想(2) 掌握最优子结构原理(3) 了解动态规划一般问题2、实验内容(1) 编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w=2，2，6，5，4,v=6,3,5,4,6(2) 合唱队形安排。【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1.Ti+1TK(1=i=K)。已知所有N位同学的身高，计算最少需要几位

2、同学出列，可以使得剩下的同学排成合唱队形。3、实验要求（1） 写出源程序，并编译运行（2） 详细记录程序调试及运行结果4、算法思想： 利用动态规划的思想，解决诸如01背包问题，最大合唱队形问题等问题的最优解，能在最短的时间内，找到最好的解决方案的一种算法。5、实验过程：1、01背包问题： 源代码如下：#include#includeusing namespace std;#define N 5#define c 10int wN+1=0,2,2,6,5,4,vN+1=0,6,3,5,4,6;int mN+1c+1;int min(int x,int y)if(x=y) return x;els

3、e return y;void KnapSack(int v,int w)int jMax=min(w1,c);for (int j=1;j=jMax;j+) /当 0=jwn时, m(n,j)=0 m1j=0;for (j=w1;j=wn时, m(n,j)=vnm1j=v1;for (int i=2;i=N;i+) /DP int jMax=min(wi,c); for (j=1;jjMax;j+) /m(i,j)=m(i+1,j) 当0=jwi mij=mi-1j; for (j=jMax;j=wn mij=max(mi-1j,mi-1j-wi+vi);void main()KnapSac

4、k(v,w);for(int i=1;i=N;i+)for(int j=0;j=c;j+)coutsetw(3)mij;coutendl;运行截图如下：合唱队形问题： 代码如下：#include #include using namespace std;#define MAXN 200void main()int n, aMAXN, bMAXN, cMAXN, i, j, max,lab,preMAXN;coutn;coutn输入n个数据：;for (i = 1; i ai;memset(b, 0, sizeof(a);memset(c, 0, sizeof(c);b1 = 1; prei=0

5、; /i=1-nfor (i = 2; i = 1; j-) if (ajmax) max = bj; prei=j; bi = max + 1; /lab:max所对应a数组元素下标 O(n)max = b1; for (i = 2; i max)max = bi;lab=i; coutLongest Increasing Subsequence is：max0 ) cj-=ai; i=prei; num-; /输出数列O(n) for(i=1;i=max;i+) coutsetw(6)ci; coutendl; 截图如下： 6.实验过程分析本次实验做的是01背包和合唱队形，之前01背包也用贪心算法讨论过，但得不到最优解，这次实验用动态规划实现的，涉及到剪枝函数部分要考虑