【蓝桥杯冲冲冲】贪心算法学习 challenge yourself ~

蓝桥杯备赛 | 洛谷做题打卡day14

• 【深基12.例1】部分背包问题

  题目描述

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

  输入格式

  第一行两个整数 $N,T$。

  接下来 $N$ 行，每行两个整数 $m_i,v_i$。

  输出格式

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

  样例 #1

  样例输入 #1

  4 50
  10 60
  20 100
  30 120
  15 45
  

  样例输出 #1

  240.00
  

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<bits/stdc++.h>
using namespace std;
struct node{//定义结构体 
    double w;//重量 
    double v;//价值 
    double p;//性价比 
}a[105];
int n;
double sum,c;
inline bool cmp(node a,node b){
    return a.p >b.p;//性价比从大到小排序 
}
int main(){
    cin>>n>>c;
    for(register int i=1;i<=n;++i){
        cin>>a[i].w>>a[i].v;
        a[i].p=a[i].v/a[i].w;//性价比=价格/重量 
    }
    sort(a+1,a+n+1,cmp);//将性价比排序 
    for(register int i=1;i<=n;++i){
        if(c>=a[i].w){//金币的重量小于或等于背包的承重量
            c-=a[i].w;//装上该堆金币后背包的剩余承重量 
            sum+=a[i].v;//金币的价值 
        }
		else{
            sum+=c*a[i].p;//如果装不下就分割金币 
            break;
        }
    }
    printf("%.2f",sum);//保留小数点后两位输出
	return 0; 
}

我的一些话

• 昨天领大家一起学习了动态规划算法初步，而这道题不要见题思意想当然以为是动态规划dp哦，虽然名为背包，但实质上是一道贪心题，多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o′ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）