文章目录
-
- 4.1 贪心概述
- 4.2 活动安排问题
- 4.3 最优装载问题
- 4.4 最优前缀码及哈夫曼算法
- 4.5 多机调度问题
- 4.6 最优分解问题
4.1 贪心概述
4.2 活动安排问题
按照 e [ ] e[] e[]从小到大将数组 e [ i ] 、 s [ i ] e[ i ]、s[ i ] e[i]、s[i] 进行排序， j j j 从 i + 1 i+1 i+1 到n开始遍历找 s [ j ] > e [ i ] s[j]>e[i] s[j]>e[i] 的活动，这个活动就可以安排在 e [ i ] e[ i ] e[i]的后面，此时让 j = i j=i j=i 更新最后一个活动，num++（num记录能安排的活动总数）
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
//冒泡排序，按照e[]从小到大将数组排序
void buble(int a[],int b[],int n)
{
int i,j;
for(i=1; i<=n; i++)
for(j=i; j<=n-i-1; j++)
{
if(a[j]<a[i])
{
int t1=a[i];
a[i]=a[j];
a[j]=t1;
int t2=b[i];
b[i]=b[j];
b[j]=t2;
}
}
}
int group(int s[],int e[],int n)//返回可安排的总活动数
{
int i=1;//取第一个
int num=1;
for(int j=i+1; j<=n; j++) //找e[i+1]>s[i]的活动数
{
if(s[j]>=e[i])
{
//printf("s[%d]=%d e[%d]=%d\n",i,i,s[i],e[i]);
// printf("s[%d]=%d e[%d]=%d\n",j,j,s[j],e[j]);
// printf("================================\n");
num++;
i=j;//找到了就将第i+1个活动赋成最后一个
}
}
return num;
}
int main()
{
int s[100],e[100];
int n;
printf("输入活动数n=");
cin>>n;
e[0]=n;
for(int i=1; i<=n; i++)
{
cin>>s[i]>>e[i];
}
buble(e,s,n);
// for(int i=1;i<=n;i++)
// printf("%d %d\n",s[i],e[i]);
cout<<group(s,e,n);
}
/*
10
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
*/
4.3 最优装载问题
更多查阅参考文章
输入：
| 物品i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 重量wi | 30 | 24 | 10 | 35 | 40 |
输出：
x[i]，判断每个箱子是否能被装入。
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
using namespace std;
//按照集装箱重量从小到大将集装箱的序号排序
void Sort(int w[],int t[],int n)
{
int temp;
for(int i=1;i<=n;i++)
t[i]=i;//默认集装箱序号升序
for(int i=1;i<=n;i++)//将轻的箱子序号前移
{
for(int j=1;j<=n;j++)
{
if(w[j+1]<w[j])
{
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
}
}
}
}
void Loading(int x[],int w[],int c,int n)
{
int t[n];
Sort(w,t,n);//得到t[]，标注从小到大的箱子序号
for(int i=1;i<=n;i++)
x[i]=0;//初始化都不能装
//i=1,w[t[i]]<c表示拿出小的箱子，判断他的重量是否小于c,小于则装入x[i]=1
for(int i=1;i<=n&&w[t[i]]<=c;i++)
{
x[t[i]]=1;
c=c-w[t[i]];//可装入的质量变小
}
}
int main()
{
int n,c;
int w[100],x[100];
cin>>n>>c;
for(int i=1;i<=n;i++)
cin>>w[i];
Loading(x,w,c,n);
for(int i=1;i<=n;i++)
cout<<x[i]<<' ';
return 0;
}
/*
5 100
30 24 10 35 40
*/
4.4 最优前缀码及哈夫曼算法
4.5 多机调度问题
参考文章
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间。
引入C++的vector知识点：
定义具有10个整型元素的向量（尖括号为元素类型名，它可以是任何合法的数据类型），不具有初值，其值不确定//定义具有10个整型元素的向量，且给出的每个元素初值为1vector<int>a(10);
vector<int>a(10,1);
按照作业时间将作业从小到大排序，每次将耗时长的作业分给当前耗时少的机器，这样就能达到最少的时间。
我们用t[i]记录第i个作业的消耗时间，machine[i]记录第i个机器当前耗时，machine_time记录当前的最小耗时，来更新index记录当前最小耗时的机器号，这样通过遍历就能更新找到最小的index以及machine_time。
#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
vector <int> t{2,14,4,16,6,5,3};//每个作业的的处理时间
int machine[100];//机器i的耗时
int mintime(int m)//m个机器
{
sort(t.begin(),t.end());//从小到大排序
int n=t.size();
int machine_time;
if(n<m)//机器的数量>作业数，时间为最长的作业时间
return t[n-1];
else
{
for(int i=n-1;i>=0;i--)//从耗时最大的作业开始分配
{
int index=0;//记录耗时最小的machine号
machine_time=machine[index];//记录最小时间
for(int j=1;j<m;j++)//找当前时间的最小machine
{
if(machine[j]<machine_time)
{
index=j;
machine_time=machine[j];
}
}
machine[index]+=t[i];
}
n=machine[0];//取最小时间
for(int i=1;i<m;i++)
n=n<machine[i]?machine[i]:n;
}
return n;
}
int main()
{
int m;//机器的数量
cin>>m;
printf("最小时间：%d",mintime(m));
}
/*
输入：
3
输出：
17
*/
4.6 最优分解问题
设n是一个正整数，现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。
输入示例
10
输出示例
30=2*3*5
输入示例
20
输出示例
2*3*4*5*6=720
若a+b=n，则|a-b|越小，那么，a*b越大。
对于能分解为多个数的n来说，分解出的数字越多且越相近则乘积越大
例如：19
分解为2，3，4，5 （5）
由于是依次递增，所以剩余5不能再分解，这4个数字全部加1，还剩1，最后一位加1即可。
#include<iostream>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
int a[100];
int Break_up(int n)
{
int n1=0,sum=0;
a[2]=2;
int i=2;//分解为2的连续数
while(n-sum>=i)
{
sum+=i;//拆解掉的数的和
a[i]=i;//将拆出来的数存到a[i];
i++;
n1++;//记录拆解的个数
}
int left=(n-sum)%n1;//未被整除的部分
for(int j=i-1; j>=2; j--)
a[j]+=(n-sum)/n1;//求出每个a[i]要加的数(整除的部分)
for(int j=i-1; j>i-1-left; j--)//从最后一个向前加
a[j]++;
return n1;
}
int main()
{
int n,n1,sum=1;
cin>>n;
n1=Break_up(n);
for(int j=2; j<n1+2; j++)
{
sum*=a[j];
(j==2)?cout<<a[j]:cout<<"*"<<a[j];
}
cout<<"="<<sum;
}
/*
输入：
8
输出：
3*5=15
输入：
19
输出：
3*4*5*7=420
*/