这个有关问题不知大家有没有好的算法

这个问题不知大家有没有好的算法
假设A、B、C、D…是不同的物品。
A = B + 2C;
B = C + 3D;
C;
D = E + 3C;
E = 5F + 2D;
F = B + C;
……

以A = B + 2C;为例，代表一个A由一个B和2个C才能够生成
C;，代表C就是自己本身组成的，不可再分解
现在已知了B, C, ...,F的个数分别是Nb, Nc, ...,Nf，有没有好一些的算法能算出这些物品总共能生成的最大的A的个数。
现在已想到的就是从B和C入手分析，每每有一个B和两个C，A的计数就增1，如果B或C没有现成的，就将B、C分解，用其它物品生成B和2C，进而生成A的方式。
不知有没有别的想法？
多谢！
[解决办法]
fa() { fb(); fc(); fc(); }
fb() { fc(); fd(); fd(); fd(); }
fc() { c++; }
fd(){fe();fc();fc();fc(); }
fe(){ff();ff();ff();ff();ff();fd();fd();}
ff(){fb();fc();}
前提，不能有闭环
[解决办法]
膜拜啊、、、
[解决办法]

引用:

fa() { fb(); fc(); fc(); }
fb() { fc(); fd(); fd(); fd(); }
fc() { c++; }
fd(){fe();fc();fc();fc(); }
fe(){ff();ff();ff();ff();ff();fd();fd();}
ff(){fb();fc();}
前提，不能有闭环

这个方法无法满足A最大值且没有考虑B\C\D..他们的个数限制。
[解决办法]
这个题目有点意思的，把我的思路分享一下，大家吐槽：

首先将题目模型化，对于x，有x = N1*x1 + N2*x2 + ... + Nn*xn，这里的x代表一个字母且它们互不相同。那么我们以x为节点建立起一颗树（好像应该叫拓扑图，反正只是为了形象化一下），根结点为A，分支结点为xi，叶子结点就是没有分支的结点。

我们来分析这个模型。
1. 自下而上，一旦我们确定了x1,x2,..,xn的个数，我们可以得到x的个数，然而我们发现，x1,x2,...,xn的个数不是确定的，为什么这么说，因为有这样的可能B = D + E, C = 2D + E，这个例子说明分配给B和C的D\E个数可以决定B和C的个数，所以D和E的个数Nd、Ne不是确定数，如果要确定D和E的个数只能通过暴力枚举。
2. 自上而下，试想，如果我们确定了x的个数会怎样，这就可以确定x1,x2,...,xn需要的个数。这样的好处是通过确定一个字母个数可以确定多个字母个数。还是上面的例子如果B需要2个，C需要3个，那么需要的D和E分别就是8个和5个。

OK，有了上面的分析，我们果断选择自上而下的方法来做，简单的说如果我们确定了A的个数，那么题目就变成了判断B\C\D...的个数是否够用了。我们可以用二分法来枚举A的个数，A的个数的max值初始化为一个很大的值使得B\C\D...的个数不够用，min初始化为0即可。

伪代码：

check tree: Na

main:
while (min < max)
if (check tree ((min+max)/2))
min = (min+max)/2
else
max = (min+max)/2

[解决办法]
首先, 还是不能有闭环
转换为线性规划问题, 假设每个公式被执行了xi次(xi>=0)
A = B + 2C;x1
B = C + 3D;x2
C=C;x3
D = E + 3C;x4
E = 5F + 2D;x5
F = B + C;x6
显然x3=0

然后对应的左边加, 右边减, 约束是加减后每类的数量>=0. 那B来举例
B0-x1+x2-x6>=0
同样的可以求到CDEF的约束.
这个题目里面的目标是 x1最大
[解决办法]
就是左边的系数乘以xi,右边的系数乘以-xi, 加在一起作为约束.
例子里面B0表示原始B的数量
然后第一个等式右边有B, 系数是1, 所以加上-x1
第二个等式左边有B, 系数是1, 所以加上x2
第六个等式右边有B, 系数是1, 所以加上-x6

整体上可以理解为, 所有的转换进行完成后, 原始B的数量加上B被产生的数量减去B被消耗的数量
结果>=0

查看更多 下一篇