最大化堡垒补给数量的策略与实现
最大化堡垒补给数量的策略与实现
- 问题描述
-
- 输入格式
- 输出格式
- 问题分析
- 解决方案
- 代码实现
- 代码解释
问题描述
可怕的战争发生了，小度作为后勤保障工作人员，为了保卫国家而努力。现在有 N 个堡垒需要补给，然而总的预算 B 是有限的。每个堡垒需要价值 P(i) 的补给，并且需要 S(i) 的运费。供应商提供了一次特别的采购优惠：小度可以选择对某次补给进行半价采购，即如果小度决定在向第 i 个堡垒提供补给时利用这一优惠，那么此次补给的采购及运输总费用将减少至 ⌊P(i)/2⌋ + S(i)。对于其他堡垒 j，补给的采购和运输费用则保持不变，即 P(j) + S(j)。请计算小度的最多能给多少堡垒提供补给？
输入格式
- 第1行2个整数：
N和B（1 ≤ N ≤ 1000，1 ≤ B ≤ 10^9）。 - 第2到
N+1行：第