本文主要是介绍sicily 10359 Valuable Jewellery,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
贪心
题意:
背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值
数据范围:
n,k<=300000,重量,价值<=10^6,背包上限<=10^8
思路:
每个背包最多只能放一个物品,那这题一下子就水了
贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物品的质量的下界,有的话就更新答案,维护map,无的就只能放弃了
题意:
背包问题,n个物品,有重量有价值.不同的是,有k个背包,每个背包有重量上限,且最多只能放一个物品.问最大价值
数据范围:
n,k<=300000,重量,价值<=10^6,背包上限<=10^8
思路:
每个背包最多只能放一个物品,那这题一下子就水了
贪心,背包用一个map存放,物品按价值递减排序.扫描每个物品,每次在map里找这个物品的质量的下界,有的话就更新答案,维护map,无的就只能放弃了
总结:贪心,优先选择物品价值高的
这篇关于sicily 10359 Valuable Jewellery的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!