看漫画学算法007：贪心算法

vlambda
2020-09-26

看漫画学算法007：贪心算法

本话内容

请输入

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100) 堆金币，第 i 堆金币的总重量和总价值分别是 mi,vi(1≤mi,vi≤100)。阿里巴巴有一个承重量为 T(T≤1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 N,T，表示有N堆金币和总承重为T的背包；

接下来 N 行，每行两个整数 mi,vi，表示每堆金币的总重量和总价值；

输出格式

一个实数表示答案，输出两位小数

#include <iostream>#include <cstdio>#include <algorithm>

using namespace std;
// 定义一个结构体，存储每堆金币的总重量和总价值// 计算它们的价值/重量比struct CB{ int w; int v;  float bl;};
// 自定义比较方法，以实现将金币按价值从高到低排序bool cmp(CB a, CB b) { return a.bl > b.bl;}
int main() { int n, t; cin >> n >> t;    // 定义一个数组来装所有的金币堆数据 CB a[n]; for (int i=0; i<n; i++) { cin >> a[i].w >> a[i].v; a[i].bl = float(a[i].v) / float(a[i].w);  }     // 将这些金币按价值从高到低排序 sort(a, a+n, cmp);     // 计算最多能拿多少 float sum = 0;    // 使用贪心算法，每次都尽可能拿最高价值的 for (int i=0; i<n; i++) {        // 如果背包满了就不能再装了 if (t==0) break; // 对于每堆金币，如果背包还能装上，则全部装上 if (a[i].w <= t) { sum+=a[i].v; t = t - a[i].w;        // 否则只装一部分，将背包装满 } else { sum+= a[i].bl * float(t); t = 0; } } printf("%.2f", sum); return 0;}