Problem

10/11

沙

Problem

修改程序，使其解决以下问题。

在抢劫一家商店时，小偷发现了 N 盒金粉。在编号为 i 的盒子中，沙子的值为 vi，重量为 wi。为了带走战利品，小偷使用背包。要求在背包的承载量受W限制的情况下，求一个劫匪能携带的沙子总成本最大。
 
你可以从盒子里倒出任意数量的沙子。那么浇注的沙子成本占整个箱子成本的比例就等于浇注沙子的体积占整个箱子体积的比例。
 
输入
输入文件的第一行包含两个数字  - N 和 W（1 <= N <= 1000，0 <= W <= 1000000）。接下来是 N 行，每行两个整数。第 i 行包含成本 vi 和权重 wi i抽屉里的沙子。所有数字均为非负数且不超过 106。
 
输出
打印期望的最大成本，误差不超过 0.0001。

 
例子
<头> <正文>

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++
# 输入 输出
1
3 50
60 20
100 50
120 30
 180.0000
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!