官方题解

【算法分析】

最优策略：每一次贪心地选当前单位重量价值最大的金币装入口袋。

【参考代码】

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
	int w, v; //w表示重量，v表示价值 
	double up; //单位重量价值 
}a[110];

bool cmp(node x, node y) {
	return x.up > y.up; //单位价值大的排在前面 
}

int main() {
	int n, m;
	cin >> n >> m;
	double ans = 0; //记录答案
	for (int i = 1; i <= n; i++) {
		cin >> a[i].w >> a[i].v;
		a[i].up = a[i].v * 1.0 / a[i].w;
	}
	sort(a + 1, a + n + 1, cmp); //排序 
	for (int i = 1; i <= n; i++) {
		if (a[i].w <= m) { //够的话全拿 
			ans += a[i].v;
			m -= a[i].w;
		}
		else { //拿上能拿的部分 
			ans += m * a[i].up;
			break; //直接退出循环 
		}
	}
	printf("%.2lf", ans);
	return 0;
}

【时间复杂度】

$O(nlog_2n)$

【预计得分】

$100pts$