100分求一个成品布优化开剪算法
求一个成品布优化开剪算法,
比如说我有200M的布,布宽1.5M,布上有许多疵点,每个疵点我们给它定一个评分,
等级标准是
一等品 100平方米的评分和<=20
二等品 100平方米的评分和<=25
三等品 100平方米的评分和>25

现在我要将给定的200M布剪为大小不等的几段,

小于20M的计为二等品,大于120M的要继续开剪.

要求使开剪后的布的一等品率最高,
请各位高手给个算法思路,非常感谢!!!


[解决办法]
问题的确比较含糊。
该问题简化一下：
有指定矩形（M 200*N 1.5）的原料，其上随机分布着许多疵点。
求最优的一维分割
约束：
必须小于120M

一等品 100平方米(66.7m)的评分和 <=20
二等品 100平方米(66.7m)的评分和 <=25
三等品 100平方米(66.7m)的评分和 >25

小于20M的计为二等品，瑕疵<=25

约束条件有如下问题：
分割小于100平方米的怎么评价等级？
等级的分级不是给定面积对应的瑕疵数量。应该是单位长度（面积）对应的瑕疵的数量。
这样的约束是没有办法使用计算机求解的，因为条件不严密。
[解决办法]
呵呵，楼主是Esquel.IT 的吗？

我认为：可以使用加权序列，序列中保存每个疵点的级别和上个疵点到这个疵点的长度。

然后的主要疵点作为开剪分界,递归向两边运算,每检测一个疵点后,检查是否等级变化,持续到三等品,再将该点作为开剪分界.

并依次计算使用每个主要疵点的开剪方案的结果。

仅供参考.
[解决办法]
‘要求使开剪后的布的一等品率最高’是指‘一等品的面积/布总面积’？
[解决办法]
首先 一个问题的解决需要经历两个阶段：物理模型 和 数学模型
物理模型是用通用的术语把问题说清楚
数学模型是用数学的语言把问题说清楚
一般有了数学模型，在问题不是很复杂的情况下，
目前的计算机水平都可以求得解答
本问题的模型存在三个主要难点：
1、物理模型的描述：包括瑕疵的描述，分割的描述，评价的描述
（这个事情究竟是怎么做的，直接解法就是模仿人的做法，求解）
2、求解模型的建立
3、分割方案的优选：什么样的分割方案才是较优的。（这个属于数学模型）

本问题的数学描述可能不是很复杂，但是解法可能有点复杂

我个人基本理解这个问题，但是要建立物理模型还是有点困难
（因为这样的问题从来没有遇到过，我可不是Esquel.IT的，哈哈）

近来很忙，没有时间静心来想。见谅。
[解决办法]
似乎描述不清楚，专业术语没解释清楚
大家都无法建立物理模型
所以无法转化成数学模型

自然无解
[解决办法]
哈哈，这个wanglj2007的出现频率比我还低。
这个问题可能还涉及 图论 的知识。
运筹学中的内容可能还不足以处理。

关于这个问题的参数，我要提问：
是将瑕疵控制在开剪的位置（将瑕疵分成两半），还是保留完整的瑕疵。
或者进一步的，瑕疵是有大小的，还是抽象为一个点。

带来数学处理上的问题：
瑕疵如果被剪开，评分如何计算？

所以大家说该问题的物理模型不清楚。

------------------------
所以让你参考图论是因为，
布可以认为是连续的空间，
瑕疵将该连续的空间，分割为离散的部分，即由连续空间变成了离散的空间。

我们要求的是这些离散空间的组合 或者 某种分割 ——这个就是分割方案（开剪方案）
使其某种属性（瑕疵评分，其实与面积这样的属性没有性质上的差异），达到最优。

可以认为是离散空间上的优化问题。

直接解法是人的解法，人有时靠的是知觉，不是科学，计算机学不会。
计算机的直接解法就是穷举（遍历），
由于是离散空间求解，
因此，
解（开剪方案）的总数是有限的。数量再大也是有限的。
因此建立 评价方法 后，用量化方法 回答 解答甲 好 还是 解答乙 好？这样的问题。
就可以直接使用穷举（遍历）求解。
[解决办法]
前日出差一周,今天刚回


处理问题本来就是要先把种种可能都考虑到,
这样是让人抓狂的

但是在细致的分析和简化的基础上,
问题得到简化和处理,这时问题趋于公式化和规范化,便不再复杂

"图论"本身就是这个知识分类的名称.因此,以图论为名的书籍就可以作为参考,
但是要注意的是,图论对于本问题是基础数学,在书里是没有本问题的直接答案的.
需要学习的是问题的描述方法和解决方法


11月-12月仍然疯狂的忙碌,所以无暇提出具体的解决方案.