石头

zhouguang

世间有5种石头ABCDE，它们可以1:1交换，但是人们更加喜欢排在前面的字母石头（最喜欢A），比如说，一个C可以随时换成一个D，但是想把一个D再直接换回一个C就不行了，必须要付出代价，那就是要同时将三个D换成三个E，也可以理解为四个D可以随时换成一个C和三个E，人们把这条规则记为：cd-3de。这种规则一共有三条，分别是：cd-3de、bc-5cd+10de、ab-7bc+21cd-35de。看最后一条规则表明：要想把一个B升级为A，需要7个B和35个D降级，当然，可以得到21个D升级的机会做为添头。人们在兑换时为了方便，在兑换前可以借贷任意数目的各类石头，但要在兑换后立即如数归还。
现在如果一个人有一个A和十个C，想得到尽量多的B，那么最多能得到几个B呢？

zeroieme

5个
尽管以1:1交换，但人们更加喜欢排序靠前，说明它们之间有细微价值差异。
\(\delta _a>\delta _b>\delta _c>\delta _d>\delta _e\)
另外3条规则以不等式表示成
\(4 \delta _d>\delta _c+3 \delta _e\)
\(8 \delta _b+56 \delta _d>\delta _a+28 \delta _c+35 \delta _e\)
\(6 \delta _c+10 \delta _e>\delta _b+15 \delta _d\)

设\(\delta _a+10 \delta _c>n_1 \delta _a+\left(11-n_1-n_3-n_4-n_5\right) \delta _b+n_3 \delta _c+n_4 \delta _d+n_5 \delta _e\)成立，可表示为前述条件的和，即\(\left(\delta _a+10 \delta _c\right)-\left(n_1 \delta _a+\left(11-n_1-n_3-n_4-n_5\right) \delta _b+n_3 \delta _c+n_4 \delta _d+n_5 \delta _e\right)=x_6 \left(\left(8 \delta _b+56 \delta _d\right)-\left(\delta _a+28 \delta _c+35 \delta _e\right)\right)+x_1 \left(\delta _a-\delta _b\right)+x_7 \left(\left(6 \delta _c+10 \delta _e\right)-\left(\delta _b+15 \delta _d\right)\right)+x_2 \left(\delta _b-\delta _c\right)+x_5 \left(4 \delta _d-\left(\delta _c+3 \delta _e\right)\right)+x_3 \left(\delta _c-\delta _d\right)+x_4 \left(\delta _d-\delta _e\right)\)

于是构成了一个整数规划
[code]Maximize[{(11-Subscript[n, 1]-Subscript[n, 3]-Subscript[n, 4]-Subscript[n, 5]),Apply[And,Flatten[{(0<=#<=11&/@{(11-Subscript[n, 1]-Subscript[n, 3]-Subscript[n, 4]-Subscript[n, 5]),Subscript[n, 1],Subscript[n, 3],Subscript[n, 4],Subscript[n, 5]}),(#>=0&/@{Subscript[x, 1],Subscript[x, 2],Subscript[x, 3],Subscript[x, 4],Subscript[x, 5],Subscript[x, 6],Subscript[x, 7]}),(#==0&/@(MonomialList[((Subscript[\[Delta], a]+10Subscript[\[Delta], c])-((11-Subscript[n, 1]-Subscript[n, 3]-Subscript[n, 4]-Subscript[n, 5])Subscript[\[Delta], b]+Subscript[n, 1] Subscript[\[Delta], a]+Subscript[n, 3] Subscript[\[Delta], c]+Subscript[n, 4] Subscript[\[Delta], d]+Subscript[n, 5] Subscript[\[Delta], e]))-(Subscript[x, 1](Subscript[\[Delta], a]-Subscript[\[Delta], b])+Subscript[x, 2](Subscript[\[Delta], b]-Subscript[\[Delta], c])+Subscript[x, 3](Subscript[\[Delta], c]-Subscript[\[Delta], d])+Subscript[x, 4](Subscript[\[Delta], d]-Subscript[\[Delta], e])+Subscript[x, 5](4 Subscript[\[Delta], d]-(Subscript[\[Delta], c]+3 Subscript[\[Delta], e]))+Subscript[x, 6]((8 Subscript[\[Delta], b]+56 Subscript[\[Delta], d])-(Subscript[\[Delta], a]+28 Subscript[\[Delta], c]+35 Subscript[\[Delta], e]))+Subscript[x, 7]((6 Subscript[\[Delta], c]+10 Subscript[\[Delta], e])-(Subscript[\[Delta], b]+15 Subscript[\[Delta], d]))),{Subscript[\[Delta], a],Subscript[\[Delta], b],Subscript[\[Delta], c],Subscript[\[Delta], d],Subscript[\[Delta], e]}]/.Subscript[\[Delta], _]->1))}]]},{Subscript[n, 1],Subscript[n, 3],Subscript[n, 4],Subscript[n, 5],Subscript[x, 1],Subscript[x, 2],Subscript[x, 3],Subscript[x, 4],Subscript[x, 5],Subscript[x, 6],Subscript[x, 7]},Integers][\code]

结果5

zhouguang

我计算的结果也是5个。1个A和10个B可以换得5个C和6个D。
题目相当于：{1,-8,28,-56,35}+3{0,1,-6,15,-10}+0{0,0,1,-4,3}+5{0,0,0,1,-1}={1,-5,10,-6,0}。