会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
题面描述
给定区域覆盖需求面积areaRequirement（单位：m²）和总预算budget（单位：元），以及 n 个可选接入点。第i个接入点的信号覆盖范围为coveragei（m²），安装成本为 costi（元）。在不超过总预算的前提下，选择若干接入点，使得覆盖总面积至少为 areaRequirement。如果有多种选择方式都满足覆盖需求，则选取总成本最小；若成本相同，则取覆盖总面积最大的方案。如果无法满足需求，则输出0。
思路
这是一个典型的「0-1 背包」变形问题：
题目内容
你需要为一个区域部署若干无线接入点，以满足整体信号覆盖要求。每个候选接入点具有两项属性：信号覆盖面积 coverage（单位：m2）和安装成本 cost（单位：元）。如果选择一个接入点，就可以获得其全部覆盖面积，同时需要支付其全部安装成本；选择多个接入点时，总覆盖面积按这些接入点的覆盖面积直接求和，总安装成本也按它们的安装成本直接求和。
给定目标：在总安装成本不超过给定预算 budget 的情况下，使总覆盖面积至少达到需求值 areaRequirement。你需要找出所有可行选择方案中实际安装成本的最小值；如果达到该最小成本时有多种方案，则报告这些方案中最大的总覆盖面积。
约束条件：
areaRequirement 满足 0<areaRequirement≤100000。budget 满足 0<budget≤10000，且 budget 是 10 的整数倍。- 候选接入点数量
n 满足 0<n≤10000。
