一个关于分割的0-1线性规划有关问题
一个关于分割的0-1线性规划问题
如果，xi是一个binary类型，只能为0和1。就像背包算法，0表示不选取，1表示选取。
每个格子有个权值(表示获利)，比如叫vi （i是 从1到n）。背包大小有上限，每个物品的重量相同（比如为1）。背包大小有限，肯定不能把上面n的全部装下。
现在要把数据分割成两部分，如图中粗黑线。（虚线是可能的分割点）
黑线两边一边全为0，另一边全为1（就是选取黑线的一边，为1 的那边）
最后求一个最大值 maximize : x1*v1 + x2 * v2 + …… xn *vn
其实这个问题用普通算法可以解（穷举分割点），但是我们算权值的时候需要整数线性规划来求（题中没说）。所以我们要求用0-1整数线性规划解。
------解决方案--------------------
没看懂。
按你的题意似乎只有两种可能。
假设有10个方格，背包能装3个货物，按你的说法只能是两种情况：装前3个或装后3个。
如果，xi是一个binary类型，只能为0和1。就像背包算法，0表示不选取，1表示选取。
每个格子有个权值(表示获利)，比如叫vi （i是 从1到n）。背包大小有上限，每个物品的重量相同（比如为1）。背包大小有限，肯定不能把上面n的全部装下。
现在要把数据分割成两部分，如图中粗黑线。（虚线是可能的分割点）
黑线两边一边全为0，另一边全为1（就是选取黑线的一边，为1 的那边）
最后求一个最大值 maximize : x1*v1 + x2 * v2 + …… xn *vn
其实这个问题用普通算法可以解（穷举分割点），但是我们算权值的时候需要整数线性规划来求（题中没说）。所以我们要求用0-1整数线性规划解。
------解决方案--------------------
没看懂。
按你的题意似乎只有两种可能。
假设有10个方格，背包能装3个货物，按你的说法只能是两种情况：装前3个或装后3个。