作者FRAXIS (喔喔)
看板Prob_Solve
标题System of Difference Constraints
时间Sun Feb 15 09:48:09 2009
线性规划的一种，针对所有的变数x1 ~ xn，存在有m条限制式，限制
式的形式都是 xi - xj < bk，其中b1 ~ bm都是整数，要求x1 ~ xn的
解的通式。
在Cormen演算法书上24.4节说此问题可以转化成shortest path问题
，就是转换成一个constraint graph，就可以求解。
但是习题24.4-11问说，如果b1 ~ bm是实数而不是整数时，而且要
求x1 ~ xn是整数，该如何求解？
习题24.4-12则是问b1 ~ bm是实数，且x1 ~ xn中只有一部分要求是
整数，该如何求解？
我想了很久还是想不太出来怎麽解决，有人知道该如何下手嘛？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.51