重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
复习-基础贪心-创新互联
贪心简介
分享题目：复习-基础贪心-创新互联
转载源于：http://cqcxhl.com/article/ceihpp.html
贪心算法正如其名，贪心，意为每次都选择一个问题的子问题的最优情况，从而达到整体上的最优情况。
但是贪心算法实际上是比较难用的，因为对于某些问题而言，每次选择最佳情况，最后不一定会达到整体上的最优情况，比如01背包问题，因为实际上01背包问题的特点就是每个个体是不可拆分的，对于贪心策略而言，必须具备无后效性，即某个状态以前的过程不会影响之后的状态。
例题1P2240 【深基12.例1】部分背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
对于部分背包问题，因为对于某一个物体，我们可以任意分割，并且其性价比不变，所以我们可以采用贪心算法，对其性价比进行排序后，从高到低依次拿取，直到拿完或者背包容量不足。属于是入门级例题
#include#include#include
using namespace std;
const int N = 1000;
struct Gold
{
double w;
double v;
double ave;
};
Gold TP[N];
bool cmp(Gold a,Gold b){
return a.ave >b.ave;
}
int main()
{
int N, T; cin >>N >>T;
float res = 0;
for (int i = 0; i< N; i++)
{
cin >>TP[i].w >>TP[i].v;
TP[i].ave = TP[i].v / TP[i].w;
}
sort(TP, TP + N,cmp);
for (int i = 0; T>0&&i P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
本题相比上题难度稍微大一点，但是也属于基础题（怎么求平均值稍微花了我一点时间）。因为如果第i人在排队，那么就同时有n-i人在等待，所以，sum+=(n-i)* V[i].first；贪心策略就不多说了。
#include#include#include
#includeusing namespace std;
const int N = 1000;
vector>V(N, { 0,0 });
bool cmp(paira, pairb)
{
return a.first< b.first;
}
int main()
{
int n; cin >>n;
double sum = 0;
for (int i = 1; i<= n; i++)
{
cin >>V[i].first;
V[i].second = i;
}
sort(V.begin()+1, V.begin()+n+1,cmp);
for (int i = 1; i<= n; i++)
{
sum += (n-i)* V[i].first;
cout<< V[i].second<< " ";
}
cout<< endl<< fixed<< setprecision(2)<< sum / n;
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享题目：复习-基础贪心-创新互联
转载源于：http://cqcxhl.com/article/ceihpp.html