关于贪心邻项交换算法中的不等式
  • 板块学术版
  • 楼主Zyque
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/7/3 22:10
  • 上次更新2023/11/6 23:42:20
查看原帖
关于贪心邻项交换算法中的不等式
116063
Zyque楼主2020/7/3 22:10

不太会处理带min或max的不等式,例如国王问题,由max(bj,aibi)<max(ajbj,bi)\max(b_j,a_ib_i)<\max(a_jb_j,b_i)得到aibi<ajbja_ib_i<a_jb_j,我是这样想的:因为bj<ajbjb_j<a_jb_j,所以只需要比较aibia_ib_imax(ajbj,bi)\max(a_jb_j,b_i);因为aibi>bia_ib_i>b_i,所以要使aibi<max(ajbj,bi)a_ib_i<\max(a_jb_j,b_i),一定有aibi<ajbja_ib_i<a_jb_j。感觉这种方法只适用于简单的情况,有没有更严谨的方法?

2020/7/3 22:10
加载中...