算法1-5的贪心策略——深基12中的背包问题

【深基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

    4 50
    10 60
    20 100
    30 120
    15 45
    
    

样例输出结构解析

00
    
    

解析

再次审视背包问题，往昔的场景仿佛又浮现在眼前，那段充满欢乐的无忧时光已悄然逝去。
每当提及背包问题，脑海中首先浮现的是01背包、完全背包、部分背包以及动态规划DP等概念