一、01背包
有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为n的背包,问背包里装入的物品具有最大的价值总和是多少?(每个物品只有一个)
(这道题是周报暑假第三周的题,这里写出来是为了与第二题进行比较)
Wi【i】:第i个物品的体积; vi【i】:第i个物品的价值; v【m】【n】:m种物品,容量为n的背包能装下的最大的价值; eg:上题中的v【5】【10】:a,b,c,d,e 5种物品,容量为10的背包装下的最大的价值是15;
思路:要使v[5][10]最大,动态规划做法时要满足最优子结构。即应当让每个物品遍历1~10的体积,让其子结构最优.每种物品2种选择:wi[i]<j(背包容量为j时)不选,否则选该物品;
边界:wi[0][j]==0,wi[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的背包,问背包里装入的物品具有最大的价值总和是多少?(每个物品无限个)
说明: Wi【i】:第i个物品的体积; vi【i】:第i个物品的价值; v【m】【n】:m种物品,容量为n的背包能装下的最大的价值; eg:上题中的v【5】【10】:a,b,c,d,e 5种物品,容量为10的背包装下的最大的价值是15;
思路:要使v[5][10]最大,动态规划做法时要满足最优子结构。即应当让每个物品遍历1~10的体积,让其子结构最优.此时每种物品不只是0、1 两种选择而是选0、1、2、3…很多次
边界:wi[0][j]==0,wi[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原因是每个物品可以被选0、1、2、3….直到k*wi[i]>n为止,并且k要从0取起,不然会出错;
三、给3个候选人投票,并统计每个候选人的票数
思路:定义结构体,赋值全部数据,再用循环给每个候选人投票
1、使用结构体输出其成员的数据时要使用“.”(成员运算符,并且在运算符中优先级别最高)
2、“-”在输出时是左对齐的意思
3、使用了strcmp函数,在开头要加上#include<string.h>
四、统计n个学生的学号、姓名、三门课程分数,求平均分最高的是哪个学生,并输出其全部数据
思路:定义结构体-赋值-求平均数-寻找分数最高的平均数-标记下标-输出结果
1、结构体声明在main函数外表示全局声明,在main函数内声明则只能在该函数内使用(和全局变量、局部变量的用法一样),所以要调用函数时需要全局声明
2、代码第34行的形参是结构体类型,其接受的是结构体变量的数据
五、
解法一:
思路:使用四层循环遍历左上角的点、遍历右下角的点,那么长宽分别b-j,a-i,如果相等则为正方形,并且个数+1,否则为长方形然后个数+1
(i,j) | ||
(a,b) |
解法二:
思路:m,n为大方格的长宽
明确公式:(就是在大方格下求子方格的长方形、正方形个数的一个公式)
正方形个数:(m-a)*(n-b),a=b
长方形:(m-a)*(n-b),a!=b
最后输出结果
学习课本第九章的内容:
已学:结构体、结构体数组、结构体指针、结构体变量做参数、结构体指针做参数、共用体、简单的链表
1、定义结构体变量:
struct 结构体名 // eg:struct student
{ 成员表列 // {int num;
}变量名列表; //char name[20]
}a;
或者
Struct 结构体名//eg:struct student
{ 成员表列//{int num;
};//char name[20]
Struct 结构体名 变量名列表;//};
//Struct student a;
2、结构体变量的初始化与引用
Struct student a={.name=“zhangfei”}; //“.”为成员运算符,优先级最高
或者
a.name={“zhangfei”};
3、结构体数组
struct 结构体名//eg:struct student 或者 struct student
{ 成员表列 // {int num; {int num;
}数组;//char name[20]; char name[20]
//}a【10】; };
struct student a【10】;
4、结构体指针(指向结构体的指针)
Struct student *p; //p可以指向Struct student类型的变量
eg:
{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的数据
注意输出方式:
1、a.成员们//eg:a.num
2、(*p).成员名 //eg:(*p).num //不能写成 *p.num
3、p->成员名 //eg:p->num
5、指向结构体数组的指针
定义:struct student a,*p;//和普通变量的指针的用法一样,
*p=&a;//只是类型不一样
输出:(*p).num a.num p->num
本周小结:这周主要学习第九章内容,结构体、结构体数组、结构体指针、结构体变量做参数、结构体指针做参数、共用体、简单的链表,但是习题比较少,很多用的不熟练,然后就是本周自己在网上找了些入门题训练,问题还有很多,需要多做题巩固知识和拓展做题的思路、积累方法。