算法设计与分析实验分析报告

任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。 1、磁带最优存储问题。 2、最优服务次序问题。

3、汽车加油问题。

提交结果：程序设计的源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include #include #include

using namespace std; using std::vector;

double greedy(vectorx,int s) {

vectorst(s+1,0); vectorsu(s+1,0); int n=x.size();

sort(x.begin(),x.end()); int i=0,j=0; while(i

st[j]+=x[i]; su[j]+=st[j]; i++; j++;

if(j==s)j=0; }

double t=0; for(i=0;i

t+=su[i]; t/=n; return t; }

void main() {

int n; int s; int i; int a; int t;

vectorx;

cout<<\请输入顾客的数量:\cin>>n;

cout<<\请输入服务员的数量:\cin>>s;

cout<<\请输入服务顾客所需时间:\for(i=1;i<=n;i++){

cout<<\cin>>a;

x.push_back(a); }

t=greedy(x, s);

cout<<\平均最短服务时间:\cin>>i; }

《算法设计与分析》实验报告

实验七 回溯策略应用基础

学号：

姓名： 班级：

日期：2014-2015学年第1学期

一、实验目的

1、深入理解回溯策略的基本思想。

2、能正确采用回溯策略设计相应的算法，解决实际问题。

3、掌握回溯算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务：从以下题目中任选一题完成，要求应用回溯策略设计解决方案。 1.连续邮资问题。 2.n后问题。 3.0-1背包问题。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include using namespace std;

class Stamp {

friend int MaxStamp(int ,int ,int []); private: int Bound(int i);

void Backtrack(int i,int r); int n;//邮票面值数 int m;//每张信封最多允许贴的邮票数 int maxvalue;//当前最优值 int maxint;//大整数 int maxl;//邮资上界 int *x;//当前解 int *y;//贴出各种邮资所需最少邮票数 int *bestx;//当前最优解 };

void Stamp::Backtrack(int i,int r) { for(int j=0;j<=x[i-2]*(m-1);j++) if(y[j]n){ if(r-1>maxvalue){ maxvalue=r-1; for(int j=1;j<=n;j++) bestx[j]=x[j]; } return; } int *z=new int[maxl+1]; for(int k=1;k<=maxl;k++) z[k]=y[k]; for(j=x[i-1]+1;j<=r;j++){ x[i]=j; Backtrack(i+1,r); for(int k=1;k<=maxl;k++) y[k]=z[k]; } delete[] z; }

int MaxStamp(int n,int m,int bestx[]){ Stamp X; int maxint=32767; int maxl=1500;