简单 的部分背包问题（贪心算法）

#include<bits/stdc++.h>
using namespace std;
const int N = 10001;
double m[N];
double v[N];
double Val[N];
double idx[N];
// 按单位价值降序排序的比较函数，起初我直接按照Val进行排序，但是未绑定m[i]和Val[i]：排序后重量和单位价值对应关系丢失
bool cmp(int i, int j) {
return Val[i] > Val[j];
}

int main() {
int n;
double t; // 定义为double，避免整数截断
cin >> n >> t;
double Sum = 0;

// 输入数据，计算单位价值
for (int i = 1; i <= n; i++) {
cin >> m[i] >> v[i];
Val[i] = v[i] / m[i]; // 单位价值=总价值/重量
idx[i] = i; // 初始化索引，用于绑定m[i]与Val[i]
}

// 按单位价值降序排序（排序索引而非直接排序Val）
sort(idx + 1, idx + n + 1, cmp);

// 贪心选物品（核心修复：用排序后的索引访问）
for (int i = 1; i <= n; i++) {
int k = idx[i]; // 排序后的第i个物品对应原数组的k号
if (t <= 0) break; // 此时背包已满，提前退出

if (m[k] <= t) {
// 能装下完整物品
t -= m[k];
Sum += v[k]; // 累加加总价值
}
else {
// 此时装剩余部分
Sum += Val[k] * t;
t = 0; // 背包装满，直接退出
}
}

// 输出结果、
printf("%.2lf\n", Sum);
return 0;
}