2019暑期通讯稿(2)——18级阶段学习篇

发布者:管理员发布时间:2019-08-21浏览次数:297


一、01背包

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为n的背包,问背包里装入的物品具有最大的价值总和是多少?(每个物品只有一个) 

(这道题是周报暑假第三周的题,这里写出来是为了与第二题进行比较)

  Wii】:第i个物品的体积;    vii】:第i个物品的价值;   vm】【n】:m种物品,容量为n的背包能装下的最大的价值;      eg:上题中的v5】【10】:abcde  5种物品,容量为10的背包装下的最大的价值是15

思路:要使v[5][10]最大,动态规划做法时要满足最优子结构。即应当让每个物品遍历1~10的体积,让其子结构最优.每种物品2种选择:wi[i]<j(背包容量为j时)不选,否则选该物品;

边界:wi[0][j]==0wi[i][0]==0,wi[0][0]==0

状态转移方程:v[i][j]=max(v[i-1][j],v[i-1][j-wi[i]]):

其中当wi[i]>j时,表示物品的体积大于此时的背包容量,所以第i个物品装不下,即此时的v[i][j]=v[i-1][j];//等于上一个物品的最大价值

wi[i]<=j时,表示物品的体积小于等于此时的背包容量,所以第i个物品装能下,即此时的v[i][j]=v[i-1][j-wi[i]]+v[i]  //能够装下第i个物品,而第i个物品占用体积wi[i],所以上一个物品的体积是j-wi[i],当装下第i个物品时,背包自然在i-1个物品的价值上多了第i个物品的价值,所以加上v[i]

由于不知道v[i-1][j],v[i-1][j-wi[i]]的大小,所以取较大的一个  

//不能理解为后者装下了第i个物品,其价值就一定最大(这个不好理解,需要多多揣摩)





二、完全背包

有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为n的背包,问背包里装入的物品具有最大的价值总和是多少?(每个物品无限个)

说明: Wii】:第i个物品的体积;    vii】:第i个物品的价值;   vm】【n】:m种物品,容量为n的背包能装下的最大的价值;  eg:上题中的v5】【10】:abcde  5种物品,容量为10的背包装下的最大的价值是15

思路:要使v[5][10]最大,动态规划做法时要满足最优子结构。即应当让每个物品遍历1~10的体积,让其子结构最优.此时每种物品不只是01 两种选择而是选0123…很多次

边界:wi[0][j]==0wi[i][0]==0,wi[0][0]==0

关键:物品的数量由原来的一个变为了无限个,从而使得转态转移方程由

v[i][j]=max(v[i-1][j],v[i-1][j-wi[i]])

变成了

v[i][j]=max(v[i-1][j],v[i-1][j-k*wi[i]]+k*vi[i]

其中0<=k*wi[i]<=n原因是每个物品可以被选0123….直到k*wi[i]>n为止,并且k要从0取起,不然会出错;

三、给3个候选人投票,并统计每个候选人的票数

思路:定义结构体,赋值全部数据,再用循环给每个候选人投票

1、使用结构体输出其成员的数据时要使用“.”(成员运算符,并且在运算符中优先级别最高)

2、“-”在输出时是左对齐的意思

3、使用了strcmp函数,在开头要加上#include<string.h>



四、统计n个学生的学号、姓名、三门课程分数,求平均分最高的是哪个学生,并输出其全部数据

思路:定义结构体-赋值-求平均数-寻找分数最高的平均数-标记下标-输出结果

1、结构体声明在main函数外表示全局声明,在main函数内声明则只能在该函数内使用(和全局变量、局部变量的用法一样),所以要调用函数时需要全局声明

2、代码第34行的形参是结构体类型,其接受的是结构体变量的数据



五、

解法一:

思路:使用四层循环遍历左上角的点、遍历右下角的点,那么长宽分别b-ja-i,如果相等则为正方形,并且个数+1,否则为长方形然后个数+1



ij





ab



解法二:

思路:mn为大方格的长宽

明确公式:(就是在大方格下求子方格的长方形、正方形个数的一个公式)

正方形个数:(m-a*n-b),a=b

长方形:(m-a*n-b),a=b

最后输出结果



学习课本第九章的内容:

已学:结构体、结构体数组、结构体指针、结构体变量做参数、结构体指针做参数、共用体、简单的链表

1、定义结构体变量:

struct 结构体名       //  egstruct student

{ 成员表列   //       {int num

}变量名列表;   //char name[20]

}a;

或者

Struct 结构体名//egstruct student

{ 成员表列//{int num

}//char name[20]

Struct 结构体名 变量名列表;//};

//Struct student a;



2、结构体变量的初始化与引用

Struct student a={.name=“zhangfei”};  //“.”为成员运算符,优先级最高

或者

a.name={“zhangfei”};



3、结构体数组

struct 结构体名//egstruct student     或者    struct student

{ 成员表列    // {int num;          {int num

}数组;//char name[20]     char name[20]

//}a10;     };

   struct student a10】;



4、结构体指针(指向结构体的指针)

Struct student *p;   //p可以指向Struct student类型的变量

eg

 struct student

{int num

char name[20]

}

struct studenta={101,“zhangfei”};

struct student  *p

p=&a

printf(“%d%s”a.num,a.name;  //输出结构体a的数据

printf(“%d%s”,(*p).num,(*p).name);//p指向a,输出的也是a的数据

注意输出方式:

1a.成员们//ega.num

2、(*p.成员名      //eg:(*p.num     //不能写成 *p.num

3p->成员名         //egp->num     



5、指向结构体数组的指针

定义:struct student a*p//和普通变量的指针的用法一样,

   *p=&a//只是类型不一样


输出:(*p.num     a.num     p->num





本周小结:这周主要学习第九章内容,结构体、结构体数组、结构体指针、结构体变量做参数、结构体指针做参数、共用体、简单的链表,但是习题比较少,很多用的不熟练,然后就是本周自己在网上找了些入门题训练,问题还有很多,需要多做题巩固知识和拓展做题的思路、积累方法。