社区讨论

求助简单贪心反例

学术版参与者 2已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@lo28hf25
此快照首次捕获于
2023/10/23 09:43
2 年前
此快照最后确认于
2023/11/03 09:57
2 年前
查看原帖
要买 nn 个物品,每个物品价格为 aia_i,有 pp 个优惠券对应 bib_i ,一个优惠券只能用一次,一个物品如果用优惠券的话价格变成ai/bia_i/b_i
求买完所有物品的最小值
我的贪心策略是最贵的物品对应 bib_i 最大的优惠券,第二贵的物品对应第二大的优惠券。一直到买完物品或者优惠券用完为止,感觉比较正确,但会有反例吗?

回复

8 条回复,欢迎继续交流。

正在加载回复...