贪心算法求解背包问题：金银岛寻宝之旅

#include #include using namespace std;

struct metal { int weight; int value; };

bool cmp(metal a, metal b) { //按单位价值从大到小排序 return a.value1.0/a.weight > b.value1.0/b.weight; }

int main() { int s, w; cin >> s >> w; metal m[s]; for(int i=0; i<s; i++) { cin >> m[i].weight >> m[i].value; } sort(m, m+s, cmp); //排序 int ans = 0; for(int i=0; i<s; i++) { if(w >= m[i].weight) { //可以放下整个金属 ans += m[i].value; w -= m[i].weight; } else { //只能放下部分金属 ans += w * m[i].value / m[i].weight; break; } } cout << ans << endl; return 0; }