C++贪心算法解决背包问题 |21xrx.com

C++贪心算法解决背包问题

2023-07-13 18:21:00 深夜i -- --

C++ 贪心算法背包问题解决

背包问题是在一定的装载容量限制下，在众多可装载物品中选择若干件放入背包中，使得物品总价值最大或总重量最小的一个问题。在计算机科学领域中，背包问题也是经典的一个问题。为了解决背包问题，出现了各种算法。其中贪心算法是一种简单且广泛使用的算法，在解决背包问题中也有着重要的应用。

C++贪心算法解决背包问题的核心思想是，在满足背包容量限制的前提下，选择单个物品价值和重量比最大的物品放入背包中。具体来说，可以将可选物品按照价值重量比从大到小排序，然后依次选择将能够放入背包的物品放入即可。

下面给出一个具体的C++贪心算法代码实现：


#include<bits/stdc++.h>
using namespace std;
struct Knapwv;
a[1005];
bool cmp(Knap a,Knap b)
  return a.wv>b.wv;
int main(){
  int n;
  double m,ans=0;
  cin>>n>>m;
  for(int i=1;i<=n;++i){
    cin>>a[i].v>>a[i].w;
    a[i].wv=a[i].v/a[i].w;
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;++i){
    if(a[i].w<=m){
      m-=a[i].w;
      ans+=a[i].v;
    }
    else{
      ans+=m*a[i].wv;
      break;
    }
  }
  cout<<fixed<<setprecision(3)<<ans<<endl;
  return 0;
}

在本代码中，Knap结构体用来记录物品的价值、重量以及价值重量比。函数cmp用来比较物品的价值重量比大小。主函数中，首先输入物品个数和背包容量，然后输入每个物品的价值和重量，并且计算出每个物品的价值重量比，存入Knap结构体中。接着，通过调用sort函数，按照价值重量比从大到小排序。最后，循环依次选择每个物品，如能够放入背包，则直接将其放入，并更新背包容量和总价值；否则，根据价值重量比计算能够放入的部分，并跳出循环。

综上所述，C++贪心算法解决背包问题，是一种简单高效的方法，可以在实际应用中得到广泛的应用。

上一篇: idea打包java可执行jar包

下一篇: C++中的while循环语句

评论区

()

相似文章