资深光能
哪位大佬有贪心的笔记
我要预习下
张岳恒在2020-04-20 12:49:47追加了内容
顶
张岳恒在2020-04-22 19:37:00追加了内容
顶
张岳恒在2020-04-25 15:05:32追加了内容
顶
高级光能
贪心笔记我倒是没有
但我有一个2019年包河区信息考试的第一题叫什么体积多少个
反正知识点是贪心
我把我的代码拿出来，有注释，你凑合着看吧应该能看懂
#include<bits/stdc++.h>
using namespace std;
int n;
int x,y,z;//箱子的长宽高
int a[10001];//a[1]表示第1件物品体积
int main(){
int i,j,k,num=0,b,c,d,s=0;
cin>>n;
cin>>x>>y>>z;
for(i=1;i<=n;i++){
cin>>b>>c>>d;
a[i]=b*c*d;//计算体积
}
//为了确保 尽可能多地放物品，我们从小到大排序
sort(a+1,a+1+n);//默认从小到大
for(i=1;i<=n;i++){
s=s+a[i];//把第i件物品入进去
if(s<=x*y*z) //当体积之和 小于箱子体积
num++;
}
cout<<num<<endl;
return 0;
}
刘欣然在2020-04-14 12:30:23追加了内容
还有一题是什么chocolate
知识点也是贪心
#include<iostream>
#include<algorithm>//排序的函数 sort
using namespace std;
struct node{
int x;//权值（一刀切下去所需要的力气 ）
bool lei;//true表示行 false表示列
}a[10010];
int cmp(node x1,node x2){
return x1.x>x2.x;
}
int n,m,ans;//ans是总的代价，初始化为0
int main(){
cin>>n>>m;
for(int i=1;i<=n+m-2;i++)//n+m-2指总共的数量
{
cin>>a[i].x;
if(i>=n)// 是列
a[i].lei=true;
else a[i].lei=false;
}
//从大到小排序
sort(a+1,a+n+m-1,cmp);//共n+m-2下标从1开始，即n+m-2+1=n+m-1
//贪心算法 权值大的先切，答案最小
int hang=1,lie=1;
//如果lei是true，即是行hang，ans+=权值x*列被切过几刀lie 行hang++
//如果lei是false，即是列lie，ans+=权值x*列被切过几刀hang 列lie++
for(int i=1;i<=n+m-2;i++){
if(a[i].lei==true){
ans+=a[i].x*lie;
hang++;
}
else{
ans+=a[i].x*hang;
lie++;
}
}
cout<<ans;
return 0;
}
/*
6 4
2 1 3 1 4
4 1 2
*/
资深天翼
1
初级启示者
所谓的“贪心算法”，就是每一次面临选择时，选择最优、最先、最X的一项，反正就是突出一个“最”字。比如有1，4，3，2，让你选两个数，令选出来的数最大，你肯定按照每次选择都选择，剩余数中最大的一个数，第一次选择4，剩下还有1，3，2，这时傻子都会选择3啊，从而得出在1，4，3，2这四个数中，选出的两数和是最大的。此时，你就不知不觉地运用到了贪心算法，以最大选择为贪心。
那么，“贪心算法”真正用到编程中是如何呢？下面用一道2013上半年软件设计师的软考题来说明这个问题。
题目是这样的：
设有M台完全相同的机器运行N个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。假设任务已经按照其运行的时间从大到小来排序，算法基于最长运行时间作业优先的策略：按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
这里要求定义的变量如下，所有数组的下标皆从0开始：
设，m是机器数，n是任务数，t[]的长度为n，其中每个元素表示任务的运行时间。s[][]长度为mn，下标从0开始，其中s[i][j]表示机器i运行的任务j的编号。d[]长度为m，其中匀速d[i]表示机器i运行的时间，count[]长度为m，其中元素count[i]表示机器i运行的任务数。max为完成所有任务的时间。min,i,j,k为临时定义变量，无意义。
考虑实例m=3（编号0-2），n=7（编号0-6)，各任务的运行时间为{16,14,6,5,4,3,2}（这里其实就是指t[i]定义为{16,14,6,5,4,3,2}，题目没有说）则求各个机器上的运行任务，从任务开始运行到完成所需要的时间。
这道题目，非常长，看起来非常让人头晕，实际上，根本一点都不难。如果你还学过《操作系统》的话，就更简单的。
意思就是将{16,14,6,5,4,3,2}这些数字扔到3个数组里面，使最终，这3个数组里面的数据之和的最大的一个，最小。你也可以想像倒水到3个杯子，要求你每次倒的水的多少只能从{16,14,6,5,4,3,2}这7个数字选一个，必须倒水倒7次，也就是这7个数字选完，最终尽可能让任一一个杯子都不溢出。
你当然是平均化倒水啊，每次倒水的时候，看哪个杯子水量最小倒哪个啊！
这时，就运用到所谓的“贪心算法”了。
最后求出来的结果是17。顺理成章就得到如下的代码，每一次选择都会有一个求最小值的过程：
#include<stdio.h>
void schedule(int m,int n,int *t){
//初始化
int i,j,k,max=0;
int d[100],s[100][100],count[100];
for(i=0;i<m;i++){
d[i]=0;
for(j=0;j<n;j++){
s[i][j]=-1;//-1代表不执行任何任务，不与第0号任务混淆
}
}
//分配前m个任务
//必然是每个机器先分别接受1个任务
for(i=0;i<m;i++){
s[i][0]=i;
d[i]=d[i]+t[i];
count[i]=1;
}
//之后判断哪个机器任务耗时最少，让其接受任务
//尽可能地并行，平均分配任务
for(i=m;i<n;i++){
int min=d[0];
k=0;
for(j=1;j<m;j++){//确定空闲机器，实质是在求当期任务总时间最少的机器
if(min>d[j]){
min=d[j];
k=j;//机器k空闲
}
}
s[k][count[k]]=i;//在机器k的执行队列添加第i号任务
count[k]=count[k]+1;//机器k的任务数+1
d[k]=d[k]+t[i];//机器k的任务执行时间+t[i]，也就是+第i号任务的耗时
}
for(i=0;i<m;i++){//确定完成所有任务需要的时间，实质是求分配完所有任务之后，耗时最多的机器
if(max<d[i]){
max=d[i];
}
}
printf("完成所有任务需要的时间：%d\n",max);
printf("各个机器执行的耗时一览：\n");
for(i=0;i<m;i++){
printf("%d:",i);
for(j=0;j<n;j++){
if(s[i][j]==-1){
break;
}
printf("%d\t",t[s[i][j]]);
}
printf("\n");
}
}
void main(){//测试用例
int time[7]={16,14,6,5,4,3,2};
schedule(3,7,time);
}
最终运行结果如下：
这里，原题目还要对上述代码进行，除去初始化、打印那两步，算法核心的时间复杂度的分析。这个很好求的，不算初始化、打印那两步，分配前m个任务，一个for循环，终止于i<m，这里复杂度为m，之后判断哪个机器任务耗时最小，两层for循环，外层终结于i<m，里层为i<n，因此为mn，最后确定所有任务需要的时间，一个for循环，终止于i<m，这里复杂度为m，也就是m+mn+m，最高维度，用现在的话来说，就是最高次元为mn，因此mn+2m~mn（此乃高等数学的内容，不会面壁去~），也就是时间复杂度为O(mn)。
然而，实际上，由于贪心算法每一次选择都要找一个最优项，遍历数组的每一项都出现一个排序，不像这里一上来就已知一个排好顺序的数组，因此时间复杂度往往是O(n2)，而要是这题给出的数组没有排好序，估计要去到O(m2n2)了。
~~~~~~~~~~~~~~~~~我是分界线~~~~~~~~~~~~~~~~~~~~~~
望采纳，谢谢！~~
中级光能
初级天翼
局部最优，能取最大就取最大
资深天翼
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
中级光能
谓的“贪心算法”，就是每一次面临选择时，选择最优、最先、最X的一项，反正就是突出一个“最”字。比如有1，4，3，2，让你选两个数，令选出来的数最大，你肯定按照每次选择都选择，剩余数中最大的一个数，第一次选择4，剩下还有1，3，2，这时傻子都会选择3啊，从而得出在1，4，3，2这四个数中，选出的两数和是最大的。此时，你就不知不觉地运用到了贪心算法，以最大选择为贪心。
那么，“贪心算法”真正用到编程中是如何呢？下面用一道2013上半年软件设计师的软考题来说明这个问题。
题目是这样的：
设有M台完全相同的机器运行N个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使得完成所有任务所需要的时间最短。假设任务已经按照其运行的时间从大到小来排序，算法基于最长运行时间作业优先的策略：按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。
这里要求定义的变量如下，所有数组的下标皆从0开始：
设，m是机器数，n是任务数，t[]的长度为n，其中每个元素表示任务的运行时间。s[][]长度为mn，下标从0开始，其中s[i][j]表示机器i运行的任务j的编号。d[]长度为m，其中匀速d[i]表示机器i运行的时间，count[]长度为m，其中元素count[i]表示机器i运行的任务数。max为完成所有任务的时间。min,i,j,k为临时定义变量，无意义。
考虑实例m=3（编号0-2），n=7（编号0-6)，各任务的运行时间为{16,14,6,5,4,3,2}（这里其实就是指t[i]定义为{16,14,6,5,4,3,2}，题目没有说）则求各个机器上的运行任务，从任务开始运行到完成所需要的时间。
这道题目，非常长，看起来非常让人头晕，实际上，根本一点都不难。如果你还学过《操作系统》的话，就更简单的。
意思就是将{16,14,6,5,4,3,2}这些数字扔到3个数组里面，使最终，这3个数组里面的数据之和的最大的一个，最小。你也可以想像倒水到3个杯子，要求你每次倒的水的多少只能从{16,14,6,5,4,3,2}这7个数字选一个，必须倒水倒7次，也就是这7个数字选完，最终尽可能让任一一个杯子都不溢出。
你当然是平均化倒水啊，每次倒水的时候，看哪个杯子水量最小倒哪个啊！
这时，就运用到所谓的“贪心算法”了。
最后求出来的结果是17。顺理成章就得到如下的代码，每一次选择都会有一个求最小值的过程：
#include<stdio.h>
void schedule(int m,int n,int *t){
//初始化
int i,j,k,max=0;
int d[100],s[100][100],count[100];
for(i=0;i<m;i++){
d[i]=0;
for(j=0;j<n;j++){
s[i][j]=-1;//-1代表不执行任何任务，不与第0号任务混淆
}
}
//分配前m个任务
//必然是每个机器先分别接受1个任务
for(i=0;i<m;i++){
s[i][0]=i;
d[i]=d[i]+t[i];
count[i]=1;
}
//之后判断哪个机器任务耗时最少，让其接受任务
//尽可能地并行，平均分配任务
for(i=m;i<n;i++){
int min=d[0];
k=0;
for(j=1;j<m;j++){//确定空闲机器，实质是在求当期任务总时间最少的机器
if(min>d[j]){
min=d[j];
k=j;//机器k空闲
}
}
s[k][count[k]]=i;//在机器k的执行队列添加第i号任务
count[k]=count[k]+1;//机器k的任务数+1
d[k]=d[k]+t[i];//机器k的任务执行时间+t[i]，也就是+第i号任务的耗时
}
for(i=0;i<m;i++){//确定完成所有任务需要的时间，实质是求分配完所有任务之后，耗时最多的机器
if(max<d[i]){
max=d[i];
}
}
printf("完成所有任务需要的时间：%d\n",max);
printf("各个机器执行的耗时一览：\n");
for(i=0;i<m;i++){
printf("%d:",i);
for(j=0;j<n;j++){
if(s[i][j]==-1){
break;
}
printf("%d\t",t[s[i][j]]);
}
printf("\n");
}
}
void main(){//测试用例
int time[7]={16,14,6,5,4,3,2};
schedule(3,7,time);
}
最终运行结果如下：
这里，原题目还要对上述代码进行，除去初始化、打印那两步，算法核心的时间复杂度的分析。这个很好求的，不算初始化、打印那两步，分配前m个任务，一个for循环，终止于i<m，这里复杂度为m，之后判断哪个机器任务耗时最小，两层for循环，外层终结于i<m，里层为i<n，因此为mn，最后确定所有任务需要的时间，一个for循环，终止于i<m，这里复杂度为m，也就是m+mn+m，最高维度，用现在的话来说，就是最高次元为mn，因此mn+2m~mn（此乃高等数学的内容，不会面壁去~），也就是时间复杂度为O(mn)。
然而，实际上，由于贪心算法每一次选择都要找一个最优项，遍历数组的每一项都出现一个排序，不像这里一上来就已知一个排好顺序的数组，因此时间复杂度往往是O(n2)，而要是这题给出的数组没有排好序，估计要去到O(m2n2)了。
缔造者之神
1
