用的是贪心策略，先用快速排序按性价比排序，再贪心选择```cpp #include using namespace std; #include double ratio(int m, int p) { return double(p / m); } void swap(double* a, int b, int c) { double t = a[b]; a[b] = a[c]; a[c] = t; } void swap(int* a, int b, int c) { int t = a[b]; a[b] = a[c]; a[c] = t; } void QuickSort(double* &pArray, int iBegin, int iEnd,int *&p,int *&m) { if (iBegin < iEnd) { int iLeft = iBegin; int iRight = iEnd; double iPivot = pArray[iBegin];

	while (iLeft < iRight)
	{
		while (iLeft < iRight && pArray[iRight] <= iPivot)
		{
			iRight--;
		}
		if (iLeft < iRight)
		{
			swap(pArray, iLeft, iRight);
			swap(p, iLeft, iRight);
			swap(m, iLeft, iRight);
			
			iLeft++;
		}

		while (iLeft < iRight && pArray[iLeft] >=iPivot)
		{
			iLeft++;
		}
		if (iLeft < iRight)
		{
			swap(pArray, iLeft, iRight);
			swap(p, iLeft, iRight);
			swap(m, iLeft, iRight);

			iRight--;
		}
	}
	pArray[iLeft] = iPivot;
	QuickSort(pArray, iBegin, iLeft - 1,p,m);
	QuickSort(pArray, iRight + 1, iEnd,p,m);
}

} double FractionalKnapsack(int n, int*& p, int*& m, int t) { double* Ratios = new double[n]; for (int i = 0; i < n; i++) Ratios[i] = ratio(m[i], p[i]); QuickSort(Ratios, 0, n - 1, p, m); double ans = 0; int j = 0; while (t > 0 && j < n) { if (m[j] <= t) { ans = ans + (double)p[j]; t = t - m[j]; } else { ans = ans + ratio(m[j],p[j])(double)t; t = 0; } j++; } return (double)ans; } int main() { int n, t; cin >> n >> t; int p = new int[n]; int* m = new int[n]; for (int i = 0; i < n; i++) cin >> m[i] >> p[i]; cout << fixed << setprecision(2)<<FractionalKnapsack(n, p, m, t)<<endl; delete[]m; delete[]p; }