贪心算法 ——————————部分背包问题

n种背包，每种背包有总价，有数量，有一个可以装m数量商品的背包，要求背包放入商品价值最大

4  7     //输入
20 3
12 6
10 3
25 5             40.00//输出

#include <bits/stdc++.h>
using namespace std;
int main() {
int a[100]; // 总价
int b[100]; // 数量/重量
double h[100]; // 单价
int c, d; // c:商品数量, d:背包容量
double v = 0; // 总价值
cin >> c >> d;
if (c <= 0 || d < 0) {
cout << fixed << setprecision(2) << 0.00 << endl;
return 0;
}
for (int i = 0; i < c; i++) {
cin >> a[i] >> b[i];
h[i] = (double)a[i] / b[i];
}
int idx[100];
for (int i = 0; i < c; i++) idx[i] = i;
sort(idx, idx + c, [&](int x, int y) {
return h[x] > h[y];
});
int s = d;
for (int i = 0; i < c; i++) {
int item = idx[i];
if (s <= 0) break;
if (b[item] <= s) {// 能装下全部
v += a[item];
s -= b[item];
} else {
double q = (double)s / b[item];
v += a[item] * q;
s = 0;
break;
}
}
cout << fixed << setprecision(2) << v << endl;
return 0;
}

代码制作不易，给博主点个赞吧！！！！！！！！！！！！！！！！！！！