P2240 【深基12.例1】部分背包问题

P2240 【深基12.例1】部分背包问题

#include <iostream>
#include <algorithm>
#include <cstdio>//OJ需要此头文件来提供printf()函数
using namespace std;
typedef struct Treasure Treasure;
struct Treasure {
	double weight;
	double value;
	double p;//weight / value
};
bool cmp(Treasure A, Treasure B) {
	return A.p > B.p;
}
int main() {
	int n, t;
	cin >> n >> t;
	struct Treasure* S = new struct Treasure[n];
	for (int i = 0; i < n; i++) {
		cin >> S[i].weight >> S[i].value;
		S[i].p = S[i].value / S[i].weight;
	}
	sort(S, S + n, cmp);
	
	double sum = 0.00;//OJ不支持C++11
	for (int i = 0; i < n; i++) {
		if (t > S[i].weight) {
			t -= S[i].weight;
			sum += S[i].value;
		}
		else {
			sum += t * S[i].p;
			break;
		}
	}
	printf("%.2lf", sum);
	return 0;
}