21xrx.com
2025-03-26 18:00:05 Wednesday
文章检索 我的文章 写文章
C++贪心算法例题分享
2023-06-24 02:59:53 深夜i     16     0
C++ 贪心算法 例题 分享

随着计算机科学技术的发展，算法作为计算机领域内的一项重要技术，日益受到广泛关注。其中，贪心算法作为一种简单而高效的算法，被广泛应用于各个领域，特别是在优化问题中。

C++作为一门流行的编程语言，也提供了许多贪心算法的实现方式。以下是一个贪心算法例题，旨在与大家分享贪心算法的实现方法和应用。

假设有n个物品和一个容量为W的背包。第i个物品的重量是wi，价值是vi。现在可以往背包里装物品，每个物品最多只能装一次。问如何选择装入哪些物品，使得背包里的物品总价值最大。

思路：

对于此类问题，很容易想到贪心算法的思想：每次选择单位价值最大的物品放入背包。这样在有限容量内可以获得最大的价值收益。

具体实现如下：

1. 将所有物品按单位价值（即单位重量的价值）进行排序，从大到小排序。

2. 依次将物品放入背包，直到背包没有容量为止。

3. 如果此时还有物品未放入背包，可以将其分割，放入部分物品。

代码实现：

#include<bits/stdc++.h>
#define MAXN 10010
double w[MAXN],v[MAXN],r[MAXN];//w-重量，v-价值，r-单位价值
int n;
double W;//背包容量
bool cmp(double a,double b)return a>b;
double solver(){
  double ans=0;
  for(int i=1;i<=n;i++)
    r[i]=v[i]/w[i];//求出单位价值
  sort(r+1,r+n+1,cmp);//排序
  for(int i=1;i<=n;i++){
    if(w[i]<=W){
      W-=w[i];//剩余容量
      ans+=v[i];//计算花费
    }
    else{
      ans+=r[i]*W;
      break;//如果背包已装满，则退出
    }
  }
  return ans;
}
int main(){
  scanf("%d%lf",&n, &W);
  for(int i=1;i<=n;i++)
    scanf("%lf%lf",&w[i],&v[i]);
  printf("%.2lf", solver());
  return 0;
}

这里使用了快速排序算法，函数sort实现的cmp函数实现了按单位价值从大到小排序。

需要注意的是，如果整件物品不能装满背包时，需要将其分割成部分物品，即按重量比例分割。 这通常通过计算单位价值与重量比的小数坐标进行排序来实现。

以上就是一道贪心算法的应用例子，希望能对大家理解贪心算法的思路和实现方式有所帮助。贪心算法是一种简单而高效的算法，在算法理解和编程实践中都有重要价值。对于想要提高自己算法能力和编程技能的同学而言，熟练掌握贪心算法的运用是必不可少的。

  
  

评论区