c++样例对,测试点全错,贪心算法,求解
查看原帖
c++样例对,测试点全错,贪心算法,求解
1070752
a13901280570楼主2024/1/18 21:30
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

typedef struct N {
	int m;//重量
	int v;//价值
	int s;//单个价值
} a;
//排序大到小
bool cmp(N x, N y) {
	return x.s > y.s;
}
int main () {
	int n, t;
	cin >> n >> t;
	vector<N> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].m >> a[i].v;
		a[i].s = a[i].v / a[i].m;
	}
	
	sort (a.begin(), a.end(), cmp);

	int q = 0;//总价值 
	for (int i = 0; i < n; i++) {
	    if (t - a[i].m >= 0) {//如果背包容量能装下最大价值金币的全部
	    	t = t - a[i].m;//就都装进去
	    	q = q + a[i].s * a[i].m;
	    } 
	    else if (t - a[i].m < 0) {//否则就能装多少是多少
	    	q = q + a[i].s * t;
	    	break;
		}
	} 
 cout << fixed << setprecision(2) << (float)q << endl;
	
	return 0;	
}
	
2024/1/18 21:30
加载中...