Module: Sorting with comparator


Problem

10/11

Sand

Problem

Modify the program so that it solves the following problem.

While robbing a store, a thief found N boxes of gold dust. In the box numbered i, the sand has a value of vi and a weight of wi. To carry away the loot, the thief uses a backpack. It is required to determine the largest total cost of sand that a robber can carry if the carrying capacity of the backpack is limited by W.
 
You can pour any amount of sand from the boxes. Then the ratio of the cost of the poured sand to the cost of the entire box will be equal to the ratio of the volume of poured sand to the volume of the entire box.
 
Input
The first line of the input file contains two numbers  - N and W (1 <= N <= 1000, 0 <= W <= 1000000). This is followed by N lines of two integers each. The i-th line contains the cost vi and the weight wi of sand in ith drawer. All numbers are non-negative and do not exceed 106.
 
Output
Print the desired maximum cost with an error of no more than 0.0001.

 
Examples
# Input Output
1
3 50
60 20
100 50
120 30
 180.0000

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

struct sand {
    int cost, weight;
    double cw;

    sand() { }
    
    sand(int _cost, int _weight) {
        this->cost = _cost;
        this->weight = _weight;
        this->cw = 1. * _cost / _weight;
    }
};

bool cmp(sand a, sand b) {  
}

vector<sand>sandArray(0);
int n;
int w;
double answer;

int main() {
    cin >> n >> w;
    sandArray.resize(n);
    for (int i = 0; i < n; i++) {
        int cost, weight;
        cin >> cost >> weight;
        sandArray.at(i) = sand(cost, weight);
    }

    sort(sandArray.begin(), sandArray.end(), cmp);

    for (int i = 0; i < n; i++)
        if (sandArray.at(i).weight <= w) {
            w -= sandArray.at(i).weight;
            answer += sandArray.at(i).cost;
        }
        else {
            answer += sandArray.at(i).cw * w;
            w = 0;
        }
        
    printf("%.4lf", answer);
}

     

Program check result

To check the solution of the problem, you need to register or log in!