C++实现0-1背包问题 |21xrx.com

C++实现0-1背包问题

2023-07-04 23:21:25 深夜i 15 0

C++ 0-1背包问题动态规划贪心算法优化策略

0-1背包问题是一个经典问题，在计算机科学中被广泛研究和应用。它的意义在于寻找最优解，即在限定重量和价值的情况下，选择最优的物品组合。本文将介绍C++语言实现0-1背包问题的方法。

首先，我们需要定义一个物品结构体，包括物品的重量和价值，并定义一个背包的容量。这些定义可以通过如下方式实现：

struct item
  int weight;
  int value;
;
const int maxCapacity = 50;

接下来，我们可以输入物品列表，并将物品按照价值排序：

int n;
cin>>n;
vector<item> itemList(n);
for(int i=0;i<n;i++){
  cin>>itemList[i].weight>>itemList[i].value;
}
sort(itemList.begin(),itemList.end(),[](item a, item b)
  return a.value>b.value;
);

然后，我们可以定义一个dp数组，并初始化前0~i的背包容量的最大价值为0，来实现动态规划：

int dp[n+1][maxCapacity+1];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
  for(int j=0;j<=maxCapacity;j++){
    if(itemList[i-1].weight<=j){
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-itemList[i-1].weight] + itemList[i-1].value);
    }
    else{
      dp[i][j] = dp[i-1][j];
    }
  }
}

最后，我们输出dp[n][maxCapacity]，其作为最大价值，即为背包问题的最优解。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
struct item{
  int weight;
  int value;
};
const int maxCapacity = 50;
int main(){
  int n;
  cin>>n;
  vector<item> itemList(n);
  for(int i=0;i<n;i++){
    cin>>itemList[i].weight>>itemList[i].value;
  }
  sort(itemList.begin(),itemList.end(),[](item a, item b){
    return a.value>b.value;
  });
  int dp[n+1][maxCapacity+1];
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=n;i++){
    for(int j=0;j<=maxCapacity;j++){
      if(itemList[i-1].weight<=j){
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-itemList[i-1].weight] + itemList[i-1].value);
      }
      else{
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout<<dp[n][maxCapacity]<<endl;
  return 0;
}

通过以上代码，我们可以成功实现C++语言下的0-1背包问题。

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

下一篇: C++如何进行动态数组内存分配？

评论区

相似文章