用c++语言贪心算法解决0-1背包问题共有n+1行输入,第一行为n值和c值,表示n件物品和背包容量c;接下来的n行,每行有两个数据表示第i(1≤i≤n)件物品的重量和价值
时间: 2023-06-18 12:06:05 浏览: 77
好的,这里是用C++语言实现的贪心算法解决0-1背包问题的代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct item {
int weight;
int value;
};
bool cmp(const item &a, const item &b) {
return a.value * b.weight > b.value * a.weight;
}
int knapsack(int n, int c, vector<item>& items) {
sort(items.begin(), items.end(), cmp);
int totalValue = 0;
int totalWeight = 0;
for (int i = 0; i < n; i++) {
if (totalWeight + items[i].weight <= c) {
totalWeight += items[i].weight;
totalValue += items[i].value;
} else {
int remainingWeight = c - totalWeight;
totalWeight += remainingWeight;
totalValue += items[i].value * ((double) remainingWeight / items[i].weight);
break;
}
}
return totalValue;
}
int main() {
int n, c;
cin >> n >> c;
vector<item> items(n);
for (int i = 0; i < n; i++) {
cin >> items[i].weight >> items[i].value;
}
cout << knapsack(n, c, items) << endl;
return 0;
}
```
其中,`item` 结构体表示一个物品的重量和价值。`cmp` 函数是排序函数,用于将物品按照单位价值(即价值/重量)降序排序。`knapsack` 函数实现了贪心算法,首先按照单位价值将物品排序,然后依次考虑每个物品,如果该物品能够全部装入背包,则将其全部装入;否则将能够装入的部分装入,并按照单位价值将剩余部分装入。最后返回总价值。
在 `main` 函数中,首先读入 n 和 c,然后读入每个物品的重量和价值,创建一个 `items` 数组表示所有物品。最后调用 `knapsack` 函数,并输出结果。