题目大意 给出nnn件商品的数量与价值，以及背包的体积www，求怎样的装载策略可以在不超过背包体积的情况下让拿取物品到达价值最大化。 题意分析 求价值最大化的物品搭配策略，要求数量总额不超过背包体积。 解题思路 根据题目给出的数据范围，每个物品的最大价值vi≤109v_i \leq 10^9vi ≤109，因此此题用背包去求解是固然求不了的。 我们不妨转换下题意，将每种商品视为si/64s_i / 64si /64个价值总额为vi×64v_i \times 64vi ×64的商品(不足64个的部分分离出来作为一个商品)，那么此题就可以由背包问题转型为贪心类型的问题。 那么当我们从价值最大往最小的去取时，此时的方案一定是最优的。先从最大到最小去取，当取完完整的个体后，再去考虑剩下不够64个的商品。最后判断取与不取哪种方法最优。 在取值的过程当中，我们可以利用优先队列进行维护不足64个的商品，在进行判断时直接取队首即可。 实现的方法很多，只需要将时间复杂度压缩至O(nlogn)O(nlogn)O(nlogn)即可。 时间复杂度解析 利用优先队列进行维护，时间复杂度为O(nlogn)O(nlogn)O(nlogn) 代码演示