sicily 10359 Valuable Jewellery

阅读：评论：0

贪心

题意:
背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值

数据范围:
n,k<=300000,重量,价值<=10^6,背包上限<=10^8

思路:

每个背包最多只能放一个物品,那这题一下子就水了

贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物品的质量的下界,有的话就更新答案,维护map,无的就只能放弃了

总结:贪心,优先选择物品价值高的

本文发布于:2024-02-03 01:37:17，感谢您对本站的认可！

本文链接：https://www.4u4v.net/it/170689543547793.html

上一篇：Codeforces —1423B. Valuable Paper（二分+网络流求最大匹配）

下一篇：A Singularly Valuable Decomposition(SVD奇异值分解)

标签：sicily Jewellery Valuable

留言与评论（共有 0 条评论）