第三次算法作业（贪心算法）

姓名：吴迪

班级：08211312

学号：08211488

班内序号 15

摘要：本文为完成作业problem1，problem3，problem4，problem5的四道贪心算法题。

备注：所有后缀为_ex的可执行文件为文件输入输出模式的程序，比如problem1_ex.exe

（所有算法实现代码承诺为本人自己编写并且截图为实际有效截图，所有程序均通过Dev-C++编译器实际测试可以运行）

problem 1

特殊的01背包（原算法分析题4-3）

问题描述：01背包是在N件物品取出若干件放在空间为C的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn，并取得最大价值。普通的01背包中物品的重量和价值没有明确的关系，这里定义一种特殊的01背包：向背包中放入的物品的价值和体积成反比，也就是价值越高，体积越小，注意这里物品价值和体积的乘积并不是固定值。例如：如下的物品满足这个“特殊的01背包”,5件物品:

物品1,价值 v=6,体积w=20

物品2,价值 v=1,体积w=60

物品3,价值 v=20,体积w=3

物品4,价值 v=15,体积w=15

物品5,价值 v=99,体积w=1

假如我有一个容量为c的背包,c=20，那么选择物品3、4、5可以获得最大价值134。

输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n和c，n代表物品的个数，c代表背包的最大容积。然后有n行整数，每行有两个整数，分别代表物品的价值v和体积w。t的范围是(1-100),n的范围是(1-100000),c、v、w的范围不超过四字节的int型。

输出：首先输出测试数据的组号，例如第一组的组号为“Case 1:”，占一行。然后是一个整数，代表可以取得的最大价值，占一行。

Sample Input:

5

5 20

6 20

1 60

20 3

15 15

99 1

1 1

100 100

5 10

92 17

101 10

93 18

109 3

87 26

10 22

96 13

96 18

89 17

106 1

71 40

86 27

83 31

78 31

106 7

68 46

15 19

54 55

103 7

82 33

75 35

99 10

94 21

53 56

95 16

91 20

39 69

82 28

54 54

110 2

42 67

65 46

Sample Output:

Case 1:

134

Case 2:

0

Case 3:

109

Case 4:

212

Case 5:

312

问题分析:

本题是特殊的01背包问题，由于其价值和重量的反比规律易证明贪婪算法的有效性，故本题可以采用贪心算法求解，即每次优选最轻物品也是最大价值物品。

源代码：（仅附文件输入输出版本，标准输入输出版本见cpp代码文件）

#include<iostream>

#include<fstream>

using namespace std;

int greedy_calculate(int* v,int* w,const int n,const int c);

int main()

{

    //input

    int t;   //test group num 1-100

    int n;   //object num 1-100000

    int c;   //capacity

    int *v;

    int *w;

    fstream in;

    fstream out;

    in.open("problem1_input.txt",ios::in);

    out.open("problem1_output.txt",ios::out);

    in >> t;

    if(t>100||t<1)

       out<<"error input of t!"<<endl;

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

        in >> n;

        if(n>100000||n<1)

           out<<"error input of n!"<<endl;

        in >> c;

        if(c<=0)

           out<<"error input of c!"<<endl;

        v=new int [n];

        w=new int [n];

        for(int j=0;j<n;j++)

        {

            in >> v[j];

            in >> w[j];

        }   

       

        //output

        out<<"Case "<<i<<":"<<endl;

        out<<greedy_calculate(v,w,n,c)<<endl;    

       

        //safety

        delete v;

        delete w;

    }

    in.close();

    out.close();

    system("pause");

    return 0;   

}

int greedy_calculate(int* v,int* w,const int n,const int c)

{

    unsigned int least_weight=-1;

    int lw_num=0;

    int count=0;

    int total_value=0;

    int total_weight=0;

    bool *x;

    x=new bool [n];

    for(int i=0;i<n;i++)

    {

       x[i]=0;       

    }

    while(total_weight<=c&&count<n){

        least_weight=-1;

        for(int i=0;i<n;i++)

        {

            if(x[i]==0){

                if(w[i]<least_weight) 

                {

                     least_weight=w[i];  

                     lw_num=i;              

                }   

            } 

        }

        x[lw_num]=1;

        total_value+=v[lw_num];

        total_weight+=w[lw_num];

        count++;

    }

    if(total_weight>c)

    {

       total_value-=v[lw_num];

       total_weight-=w[lw_num];                 

    }

   

    delete x;

    return total_value;

}

运行截图

      

使用generate后产生的测试用例：

problem 3

最大边权最小生成树（原算法分析题4-12）

问题描述：已知图G是一个联通的图，请你构造一颗生成树，这颗生成树上最长的边比该图G的其他生成树的最长边都要小。例如,图G的邻接矩阵如下:

0 498 49

498 0 682

49 682 0

如图：

有生成树1：

生成树2：

生成树3：

这三课生成树的最大边权分别为498、682和682，所以第一课生成树的最大边权最小，应选第一棵树。现在你的任务是，根据图的邻接矩阵，计算该图的最大边权最小的生成树的最大边长，如上例的计算结果为498。

输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是一个正整数n，n代表图G的顶点个数，n的范围是1-1000。然后有n行整数，每行有n个整数，即为图的邻接矩阵。

输出：首先输出测试数据的组号，例如第一组的组号为“Case 1:”，占一行。然后是一个整数，代表该图的最大边权最小的生成树的最大边长，占一行。

Sample Input:

5

5

0 735 749 172 215

735 0 259 493 738

749 259 0 469 309

172 493 469 0 38

215 738 309 38 0

3

0 498 49

498 0 682

49 682 0

2

0 531

531 0

5

0 257 551 743 659

257 0 697 783 758

551 697 0 320 533

743 783 320 0 708

659 758 533 708 0

6

0 632 408 364 719 156

632 0 535 285 766 379

408 535 0 374 235 687

364 285 374 0 411 853

719 766 235 411 0 536

156 379 687 853 536 0

Sample Output:

Case 1:

309

Case 2:

498

Case 3:

531

Case 4:

551

Case 5:

374

算法分析：

本题为最大最小生成树问题，因此涉及的图的边和点的保存方式等诸多问题，另外还要检测图的连通性，贪心算法每次去掉权值最高的边，然后看剩下的边是否仍能确保图的连通性，如果能，则必定可以生成一棵最小生成树，此时的最大边权就是去掉后剩下的最大边，继续这样检测直到不能连通，此时去掉的边就是必须保留的最大边。

源代码

#include<fstream>

#include<iostream>

using namespace std;

typedef struct Edge

{

   int length;

   int p1;

   int p2;      

}edge;

void sort_edges(edge * e,int * order,int m);

int find_max(edge * e,int * order,int m,int n);

fstream in;

fstream out;

int main()

{

    int t;   

    int n;  //点数

    int m;  //边数

    int value;

    int waste;

    edge *e;

    int *order;  //从大到小逆序排

   

    in.open("problem3_input.txt",ios::in);

    out.open("problem3_output.txt",ios::out);

   

    in>>t;

    if(t<1||t>100000)

       cout<<"error input!"<<endl;

   

    for(int i=0;i<t;i++)

    {

       in>>n;

       int p=0;

       if(n<1||n>1000)

       cout<<"error input!"<<endl;

       m=n*(n-1)/2;

       e=new edge [m];

       order= new int [m];

       for(int j=0;j<n;j++)

       {

          for(int k=0;k<n;k++){

             if(k>j){

                in>>value; 

                e[p].length=value;

                e[p].p1=j;

                e[p++].p2=k;

             }

             else

                in>>waste;    

          }

       }  

       sort_edges(e,order,m);

       /*show edges

       cout<<"edges:"<<endl;

       for(int j=0;j<p;j++)

       {

          cout<<e[order[j]].length<<" "<< e[order[j]].p1<<" "<< e[order[j]].p2<<endl;      

       } */

      

       cout<<"Case "<<i+1<<":"<<endl;

       cout<<find_max(e,order,m,n)<<endl;

      

       delete order;

       delete e;

    }

    in.close();

    out.close();

    system("pause");

    return 0;   

}

void sort_edges(edge * e,int * order,int m)

{

   int * x;

   int max=0;

   x = new int [m];

   int p;

   for(int i=0;i<m;i++)

      x[i]= 0;

   for(int i=0;i<m;i++)          

   {

      max=0;

      for(int j=0;j<m;j++){     

          if(x[j]==0){

             if(e[j].length>max){

                 max=e[j].length; 

                 p=j;

             }  

          }

      }

      order[i]=p;   //order i 记录第 j 个元素

      x[p]=1;

   }       

                              

   delete x;

}

int find_max(edge * e,int * order,int m,int n)

{

   int *w;  //标记边是否在图里

   int p;

   int **matrix;

   matrix=new int*[n];

   for(int i=0;i<n;i++)

      matrix[i]=new int [n];

   w=new int [m];

   for(int i=0;i<m-n+2;i++) 

   {  

      for(int j=0;j<m;j++)

      {

         w[j]=1;   

      }

      for(int j=0;j<=i;j++)

      {

         w[order[j]]=0;    

      }

      for(int j=0;j<n;j++)

      {

         for(int k=0;k<n;k++)

         {

             if(j==k)

                matrix[j][k]=1;   

             else

                matrix[j][k]=0;   

         }           

      }

     

      for(int j=i+1;j<m;j++)          //获取连通性矩阵

      {

         if(w[order[j]])

         {

             int ps1;

             int ps2;

             ps1=e[order[j]].p1;   

             ps2=e[order[j]].p2;

             matrix[ps1][ps2]=1;

             matrix[ps2][ps1]=1;            

         }      

      }

  

      int step=1;int zero=1;int newl=0;

      while(zero==1){

          newl=0;

          zero=0;

          for(int j=1;j<n;j++){       //检验第step步增加的点

             if(matrix[0][j]==step)

             {

                for(int k=1;k<n;k++)

                {

                   if(matrix[j][k]>=1&&matrix[0][k]==0)

                   {

                       matrix[0][k]=step+1; 

                       newl=1;                                   

                   }       

                }                 

             }

             if(matrix[0][j]==0)

                zero=1;

          }

          step++;

          if(newl==0)

             break;

      }

      if(newl==0&&zero==1){

           delete w;           

           for(int j=n-1;j>=0;j--)

              delete [] matrix[n];

           delete []matrix;

     

          return e[order[i]].length;

      }

      else if(zero==0);

   }   

   delete w;           

   for(int i=n-1;i>=0;i--)

      delete [] matrix[n];

   delete []matrix;

   return 0;  //e[order[0]].length

}

运行截图

此为实验所给的测试用例，为简便采用了文本的输入输出，而generate产生的输入文件由于我的算法复杂度可能太高，因此输出时间太长。

最优合并（原算法实现题4-2）

问题描述：已知k个排好序的序列S1,S2,…,Sk，第i个序列的长度为Li。使用2路归并算法将这k个序列合并成一个序列。假设采用2路归并排序算法将长度为n和m的序列合并需要m+n-1次比较，那么将k个序列合并，每次合并两个序列，最多和最少需要多少次比较？

例如有4个序列，长度为5,12,11,2

合并时的过程(其中的一种方式)：

5与2合并，需比较6次，合并后序列长度为7,12,11。

7与11合并，需比较17次，合并后序列长度为18,12。

12与18合并，需比较29次，合并后序列长度为30。

最终比较6+17+29=52次。

输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是一个正整数n，n代表序列的个数。然后有n个整数，代表n个序列的长度，即Li。n的范围是1-100000，注意最终结果可能超过int型范围，请使用long long类型存储结果。

输出：首先输出测试数据的组号，例如第一组的组号为“Case 1:”，占一行。然后是两个整数，代表合并后最多比较次数与最少比较次数。

Sample Input:

5

6

10 64 90 75 49 4

7

70 29 34 84 93 2 11

8

94 42 83 50 67 17 7 20

2

30 82

8

42 45 26 34 28 27 61 15

Sample Output:

Case 1:

1247 656

Case 2:

1653 771

Case 3:

2153 1024

Case 4:

111 111

Case 5:

1417 807

源代码

#include<iostream>

#include<fstream>

using namespace std;

void swap(long a[],int i,int j);//from the old programe lib

int partition(long a[],int p,int r);

void QuickSort(long a[],int p ,int r);

void insert(long *l,int s,int n);     //insert l[s] to sorted list

long long max(long *l,int n,bool sorted);

long long min(long *l,int n,bool sorted);

int main()

{

    int t;   

    int n;

    long *l;

    long long best;

    long long worst;

    fstream in;

    fstream out;

    in.open("problem4_input.txt",ios::in);

    out.open("problem4_output.txt",ios::out);

    in>>t;

    if(t<1||t>100000)

       out<<"error input!"<<endl;

   

    for(int i=0;i<t;i++)

    {

       in>>n;

       if(n<1||n>100000)

       out<<"error input!"<<endl;

       l=new long [n];

       for(int j=0;j<n;j++)

          in>>l[j];            

       out<<"Case "<<i+1<<":"<<endl;

       best=min(l,n,0);      

       worst=max(l,n,1);

       out<<worst<<" "<<best<<endl;      

       delete l;

    }

    in.close();

    out.close();

    system("pause");

    return 0;   

}

void swap(long a[],int i,int j)

{

   int temp=a[i];

   a[i]=a[j];

   a[j]=temp;  

}

int partition(long a[],int p,int r)

{

   int i=p,j=r+1;

   long x=a[p];//普通快排

   int mid=(p+r+1)/2;

   // raise order

   while(true)

   {

      while(a[++i]<x&&i<r)  ;

      while(a[--j]>x)   ;

  

      if(i>=j) break;

      swap(a,i,j);

   }      

   a[p] =a[j];

   a[j] = x;

   return j;

}

void QuickSort(long a[],int p ,int r)

{

    if (p < r)

    {      

       int q= partition(a, p , r);

       QuickSort(a,p,q-1);

       QuickSort(a,q+1,r);     

    } 

}

long long max(long *l,int n,bool sorted)

{

    long long result=0;

    long long length=0;

    if(sorted);

    else

       QuickSort(l,0,n-1);

   

   

    length=l[n-1];

    for(int i=n-2;i>=0;i--)

    {

        length+=l[i];

        result+=length;

        result--;      

    }   

    return result;

}

void insert(long *l,int s,int n)     //insert l[0] to sorted list

{

   int i;

   for(i=s+1;i<n;i++)

      if(l[i]>l[s])

      {      

         break;         

      } 

   i--;

   long temp=l[s];

   for(int j=s;j<i;j++)

   {

       l[j]=l[j+1];           

   } 

   l[i]=temp;

}

long long min(long *l,int n,bool sorted)

{

    long long result=0;

    long length=0;

   

    if(sorted);

    else

        QuickSort(l,0,n-1);

   

    long *cl;

    cl=new long [n];

    for(int i=0;i<n;i++)   //拷贝l数组

   

        cl[i]=l[i];

    //类似huffman的最小合并策略

    length=cl[0];

    for(int i=1;i<n;i++)

    {

        length+=cl[i];

        result+=length;

        result--; 

        cl[i]=length; 

        insert(cl,i,n); 

        length=cl[i];

    }     

    return result;

}

运行截图

generate

prblem5

汽车加油（原算法实现题4-9）

问题描述：一辆汽车加满油后可行驶n km。旅途中有若干个加油站，加油站的个数为k。

在经过k个加油后是目的地。假设汽车出发地、k个加油站、目的地在一条直线上。已知出发地到第一个加油站的距离、每个相邻加油站的距离(第k个和第k+1个加油站的距离)、最后一个加油站和目的地的距离，求汽车最少加油的次数。

例如：n=7,k=7,然后是8个整数：

1 2 3 4 5 1 6 6

在这里1代表出发地到第一个加油站的距离。

2、3、4、5、1、6、6代表第1个到第2个、第2个到第3个、…、第6个到第7个、第7个加油站到目的地的距离。那么可知汽车至少要在第3、4、6、7个加油站加油，才可到达目的地。当然不排除到不了下一个加油站的情况。具体如图：

输入：首先是一个整数t,代表测试数据的组数。每组测试数据首先是两个正整数n、k，n代表汽车加满油后可行驶n km，k代表加油站的个数。然后有k+1个整数，含义如题目描述。k的范围是1-100000。

输出：首先输出测试数据的组号，例如第一组的组号为“Case 1:”，占一行。然后是一个整数，代表合并后最多比较次数与最少比较次数。

Sample Input:

5

20 9

2 2 12 3 2 9 2 12 9 3

12 2

10 9 9

12 3

7 10 2 9

10 7

11 5 8 5 8 10 10 6

15 10

2 9 2 12 8 3 12 1 5 10 1

Sample Output:

Case 1:

3

Case 2:

2

Case 3:

2

Case 4:

No solution.

Case 5:

5

源代码

#include<iostream>

#include<fstream>

using namespace std;

int count_time(int d[],int k,int n);

int main()

{

    int t=0;

    int n;

    int k;

    int *d;

    fstream in;

    fstream out;

    in.open("problem5_input.txt",ios::in);

    out.open("problem5_output.txt",ios::out);

   

    in>>t;

    if(t<1)

       out<<"error input"<<endl;

    for(int i=0;i<t;i++)

    {

        in>>n;     // n kilometers to go

        if(n<1)

          out<<"error input"<<endl;    

        in>>k;     // number of gas station

        if(k<1||k>100000)   

          out<<"error input"<<endl;   

        k++; 

        d = new int [k];

        for(int j=0;j<k;j++)

        {

           in>>d[j];       

        }  

        int result=count_time(d,k,n);

        //output

        out <<"Case "<<i+1<<":"<<endl;

        if(result>=0)

           out <<  result<<endl; 

        else

           out <<  "No solution."<<endl;

        delete d;

    }

    in.close();

    out.close();

   

    system("pause");

    return 0;   

}

int count_time(int d[],int k,int n)  //-1 reprent unreachable

{

    int time=0;

    int oil=n;

    for(int i=0;i<k;i++)

    {

       while(d[i]<oil){

          oil-=d[i];  

          i++; 

          if(i>=k)

             return time;           

       }

       if(d[i]>n){

          return -1;

       }

       i--;

       //oil+=d[i];  //恢复

       oil=n;

       time++;          

    }

    return time; 

}

运行截图