求助简单贪心反例
  • 板块学术版
  • 楼主little_kongbai
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/7/14 11:14
  • 上次更新2023/11/3 09:57:16
查看原帖
求助简单贪心反例
232205
little_kongbai楼主2023/7/14 11:14

要买 nn 个物品,每个物品价格为 aia_i,有 pp 个优惠券对应 bib_i ,一个优惠券只能用一次,一个物品如果用优惠券的话价格变成ai/bia_i/b_i

求买完所有物品的最小值

我的贪心策略是最贵的物品对应 bib_i 最大的优惠券,第二贵的物品对应第二大的优惠券。一直到买完物品或者优惠券用完为止,感觉比较正确,但会有反例吗?

2023/7/14 11:14
加载中...