2023年8月1日发(作者：)

算法分析与设计

实验03

实验目的

掌握动态规划算法，简单0-1背包问题；

掌握最优二叉搜索树的算法。

掌握贪心算法的贪心选择性质和最优子结构性质；

掌握最多活动安排问题，散装背包问题和最优装载问题的贪心算法。

实训内容

1、 简单0-1背包问题：给定一个背包，其容量是10千克，5件物品，其重量分别是4，6，3，5，8公斤；其价值分别是：9，3，6，13，15元，试根据动态规划算法给出0-1背包问题的最优解以及相应的求解过程（要求给出跳跃点的变化情况）。

2、 散装背包问题：给定一个背包，其容量是10千克，5件物品，其重量分别是4，6，3，5，8公斤；其价值分别是：9，3，6，13，15元，试根据贪心算法给出散装背包问题的最优解以及相应的求解过程。

3、 编写一个程序，完成如下要求：

1） 随机生成10000个字符（字符包括：a, b, c, d, e和f），并将这10000个字符存储在名称为的文件中，并输出该文件的长度（单位：bit）。

2） 统计上述a, b, c, d, e和f各字符出现的次数。

4、 随机选择上题生成的2次结果，采用哈夫曼编码对文件的各个字符进行编码，并计算同原始文件的压缩比率。

// 实验 : Defines the entry point for the console application.

//

#include

#include"string"

#include

#include

using namespace std;

string get(int length)

{

1 srand((unsigned)time(NULL));

string s;

for(int i=0;i

s+='a'+rand()%6;

}

return s;

}

void main(){

string s;

s=get(100);

int a=0;

int b=0;

int c=0;

int d=0;

int e=0;

int f=0;

/*

fstream fp;

("C:",fstream::in|fstream::out|fstream::app);

(0,ios::end);

cin>>s;

fp<

();*/

ofstream output;

("c:/");

output<

ifstream input;

("c:/");

cout<

for(int i=0;i<100;i++){

if(s[i]=='a') a++;

if(s[i]=='b') b++;

if(s[i]=='c') c++;

if(s[i]=='d') d++;

if(s[i]=='e') e++;

if(s[i]=='f') f++;

}

2 cout<

cout<<"a的数目"<

cout<<"b的数目"<

cout<<"c的数目"<

cout<<"d的数目"<

cout<<"e的数目"<

cout<<"f的数目"<

}

3

2023年8月1日发(作者：)

算法分析与设计

实验03

实验目的

掌握动态规划算法，简单0-1背包问题；

掌握最优二叉搜索树的算法。

掌握贪心算法的贪心选择性质和最优子结构性质；

掌握最多活动安排问题，散装背包问题和最优装载问题的贪心算法。

实训内容

1、 简单0-1背包问题：给定一个背包，其容量是10千克，5件物品，其重量分别是4，6，3，5，8公斤；其价值分别是：9，3，6，13，15元，试根据动态规划算法给出0-1背包问题的最优解以及相应的求解过程（要求给出跳跃点的变化情况）。

2、 散装背包问题：给定一个背包，其容量是10千克，5件物品，其重量分别是4，6，3，5，8公斤；其价值分别是：9，3，6，13，15元，试根据贪心算法给出散装背包问题的最优解以及相应的求解过程。

3、 编写一个程序，完成如下要求：

1） 随机生成10000个字符（字符包括：a, b, c, d, e和f），并将这10000个字符存储在名称为的文件中，并输出该文件的长度（单位：bit）。

2） 统计上述a, b, c, d, e和f各字符出现的次数。

4、 随机选择上题生成的2次结果，采用哈夫曼编码对文件的各个字符进行编码，并计算同原始文件的压缩比率。

// 实验 : Defines the entry point for the console application.

//

#include

#include"string"

#include

#include

using namespace std;

string get(int length)

{

1 srand((unsigned)time(NULL));

string s;

for(int i=0;i

s+='a'+rand()%6;

}

return s;

}

void main(){

string s;

s=get(100);

int a=0;

int b=0;

int c=0;

int d=0;

int e=0;

int f=0;

/*

fstream fp;

("C:",fstream::in|fstream::out|fstream::app);

(0,ios::end);

cin>>s;

fp<

();*/

ofstream output;

("c:/");

output<

ifstream input;

("c:/");

cout<

for(int i=0;i<100;i++){

if(s[i]=='a') a++;

if(s[i]=='b') b++;

if(s[i]=='c') c++;

if(s[i]=='d') d++;

if(s[i]=='e') e++;

if(s[i]=='f') f++;

}

2 cout<

cout<<"a的数目"<

cout<<"b的数目"<

cout<<"c的数目"<

cout<<"d的数目"<

cout<<"e的数目"<

cout<<"f的数目"<

}

3