为了振奋士气,刘备 关羽和张飞在桃园设宴款待士兵
三兄弟最爱的菜肴是蛇羹 宫保田鸡和麻婆豆腐。
他们对各样菜肴有不同的喜爱、 享受程度
而盛放菜肴的碟子大小也各有不同 他们希望在他们桌子上尽量多地放置这三道菜
使碟子占位不超出桌子,又使享受程度最高
士兵的宴席当中,他们有更多的菜式和更宽的桌子 但他们也面临类似的问题
面对难题,刘备取出神算法板求助
在出兵之前,我们的英雄安排了一个桃园宴会 目的就是要把军队里面的士气提高
怎么可以把士气提高呢?最重要就是每个人都开心
怎么开心呢?食物的满意度就是其中一个很重要的指标了
所以我们的英雄呢,为了自己也开心
所以他们就希望在他们的桌子上面放满 他们、
三种他们都很喜欢的菜 包括这个蛇羹、
宫保田鸡跟这个麻婆豆腐 每一道菜也有一个满足的程度
也有它们的大小。
但是呢 他们的桌子有一定的容量的,是
18 根据我们现有的数据呢,我们的模型应该就是下面这个
它这个模型有三个变量分别就是 S F 跟
M,就是不同的菜,我们要 放多少盘。
然后这个 总和呢,就是基于不同菜的满足的程度
然后要多少盘呢,这个总和就是总的满足的程度了
然后我们当然有一个约束,这个约束呢,就是要求 我们每一道菜要选多少盘呢,它们的
大小加起来一定要小于等于这个 18。
这个就是桌子的容量了 当然也需要为我们的士兵准备他们喜欢的菜
士兵呢,他们的桌子的容量是 70 他们有更大的桌子,而且他们喜欢的菜呢,有五道
每一道菜也分别有它们的满足的程度,也有它们的大小 我们看见这个是另外一个问题
但是跟之前的问题呢,是差不多是一模一样的 所以我们希望可以建一个可以对于不同规模的
数据可以重复使用的一个模型出来 这个就是我们桃园宴会的一个模型了
首先,我们有一个枚举类型的数据来表示不同的菜 然后,有一个
capacity 来代表我们桌子的大小的容量 然后我们就看见一个新的概念了。
这个新的概念呢,就是一个数组的声明 一个数组呢,其实就是一个列。
它的下标就是不同的菜 每一个元素就代表每一道菜 它的满足程度。
我们也有另外一个数组,这是代表每一道菜 它的大小。
我们也有一个 变量的数组。
这个变量的数组呢,就代表每一道菜
到底我们可以放多少盘在我们的桌子上面 就是 amount。
好了,我们还有另外一个新的概念 就是我们有
每一道菜 i,我们利用这个菜 i 呢
来作为这个 amount、 这个变量数组的查找
而且呢,这个是放在一个 forall 的表达式里面的,里面的意思就是
给我们每一道菜 i,我们要求呢 这一道菜
i 呢,它的盘子的数目不小于
0 我们下面的一条约束跟我们的
目标函数呢,也有一个新的概念出来就是 sum。
sum 呢,它意思就是把每一道菜
i 它的大小跟它的盘数的乘积呢 加起来。
我们要求呢,这个是小于等于我们桌子的容量
在我们的目标函数里面就是要求把所有的不同的菜,它的满足程度
乘以这个它的盘数。
我们需要把这个最大化 我们刚才看见一些
MiniZinc 的新的特性。
最重要就是数组了 数组的下标范围的表达式呢,可以有两种
第一,我们就可以利用一个很简单的 l..u 这个范围 这个
l 跟 u 呢,都应该为这个整数来的 它们的下标范围呢,也可以用一个枚举类型来表示
我们要声明一个变量 还是参数的数组呢,我们用的语法就是这样子:
array 一个范围 of 一个变量还是一个参数的声明
然后,我们要为这个数组查找的 就是个数组的名字,跟一个下标的表达式
有了数组之后,我们就可以利用不同的生成器的表达式了 我们这个
forall 的意思是什么呢?就是要求在这个
范围之内的每一个 i 它的对应的 布尔式、
布尔型的表达式都为真 这个就是 forall 要求的。
sum(i in 范围) (表达式) 是什么意思呢?我们就是把这个范围里面每一个不同的
i 的值 把它对应的表达式的值加起来,求它的总和就是
sum,帮我们 可以做的东西了
我们有了我们的模型,我们就可以 建我们第一个数据的文件,就是基于我们的
英雄他们喜欢的菜,而且他们 用的桌子不同菜的满足的程度,还有
不同菜的大小,然后要求这个 MiniZinc
运行,求了这个解出来 这个解呢 这个虚线代表我们找到一个解。
这个等号组成的虚线就是证明了我们已经 找到最优的解出来了。
这个解就要求我们要可以放一盘的蛇羹 两盘的宫保田鸡。
我们建另外一个数据文件,就是代表我们的士兵喜欢的菜
也有不同菜的满足程度啊跟它的大小 要求这个 MiniZinc
把这个模型跟数据 跑一下,这个就是我们找到的最优的解了
当然了,你们也可以选择使用我们的 IDE 来要求这个
MiniZinc 去跑我们的模型跟数据 我们在这个问题里面学会的一个很重要的概念
就是怎么样给这个对象来建模
我们首先需要来创建一个枚举类型来为我们的对象命名,譬如说 在我们的问题里面就是
DISH 这个枚举类型的数据呢,就是代表我们不同的菜
然后我们需要创建一个参数的数组来表示我们每一个
对象的一些不同的属性 譬如说,我们每一道菜的大小、 每一道菜它们的满足程度
也需要创建一个变量的数组来代表我们每一个对象
的每一个决策,譬如说在我们的 例子里面呢,就是这个
amount 就是代表每一道菜 我们需要多少盘
然后,我们可以使用 生成器表达式或者是推导式来
建立限制对象的一些约束 我们也需要注意就是一个模型里面
可能包含多余一个的对象集合的 我们来一个小结
枚举类型可以令我们很方便来表示对象集合
我们给我们对象集合定义的数组呢,可以帮助我们来代表
这个对象不同的特性,也有不同的决策 我们利用
forall 跟 sum 可以帮助我们 去构造可以约束多个对象的表达式
我们这个桃园宴会的问题,其实是一个众所周知的一个背包问题的一个版本
[空白_录音] [空白_录音]