求一算法（关于配方成本核算的）

Question

呵呵，純屬接分
如果LZ是SA/SD，那接手的programmer要哭死了

Answer 1

结构：
表1
YSA001 varchar（10）--元素编号
YSA002 varchar（20）--元素名称
YSA003 varchar（1）--是否杂质
表2
主表：
CLA001  varchar（10）--材料编号
CLA002  varchar（20）--材料名称
CLA003  numeric(14,6)--材料单价
从表：
CLB001  varchar（10）--材料编号
CLB002  varchar（10）--元素编号
CLB002  numeric(14,4)--元素比例
表3
主表：
CPA001 varchar（10）--产品编号
CPA002 varchar（20）--产品名称
从表
CPB001 varchar（10）--产品编号
CLB002  varchar（10）--元素编号
CLB002  numeric(14,4)--元素比例
其实就是根据产品的元素比例，求生产产品要使用哪些原料，保证原料的总成本是最低的；

Answer 2

create table ys(id int,fh varchar(10),mc varchar(20))
insert ys select 1,'Cu','铜' union select 2,'Nr','镍' 
union select 3,'Mn','锰' union select 4,'Fe','铁' union select 5,'C','炭－杂质'
create table cl(id int,mc varchar(20),jg int)
insert cl select 1,'16镍铁合金',10 union select 2,'10镍铁合金',20 union select 3,'12镍铁合金',30 
union select 4,'电解Cu（纯铜)',40 union select 5,'废铁（纯铁）',50
create table clcf(clid int,cfid varchar(10),hl int)
insert clcf select 1,1,2 union select 1,2,16 union select 1,3,0 union select 1,4,77 union select 1,5,5
union  select 2,1,1 union select 2,2,10 union select 2,3,0 union select 2,4,83 union select 2,5,6
union  select 3,1,1 union select 3,2,12 union select 3,3,0 union select 3,4,82 union select 3,5,5
union  select 4,1,100 union select 4,2,0 union select 4,3,0 union select 4,4,0 union select 4,5,0
union  select 5,1,0 union select 5,2,0 union select 5,3,0 union select 5,4,100 union select 5,5,0
create table cp(id int,mc varchar(20))
insert cp select 1,'201号铁'
create table cpcf(cpid int,cfid int,hl int)
insert cpcf select 1,1,0 union select 1,2,8 union select 1,3,0 union select 1,4,90 union select 1,5,2
go
declare @clid int,@cfid int,@hl int,@yl dec(38,6)
select cfid,hl hl into #y from cpcf where cpid = 1 and hl <> 0
select clid,cfid,jg,hl into #all from clcf ,cl  where cfid in(select cfid from #y) and clid = id and hl <> 0
create table #r (clid int,hl dec(38,6))
while exists (select 1 from #y)
begin
 select @hl=max(hl) from #y
 select top 1 @cfid = cfid from #y where hl=@hl
 select top 1 @clid = clid,@yl = @hl*1.0/hl from #all 
 where hl*1.0/jg = (select max(hl*1.0/jg) from #all where cfid = @cfid) and cfid = @cfid
 insert #r select @clid,@yl 
 update #y set hl = a.hl - @yl*b.hl from #y a,#all b where a.cfid = b.cfid and b.clid = @clid
 delete #y where hl <=0 
end
select b.mc 材料,20*a.hl 需要数,20*a.hl*b.jg 成本 from #r a,cl b where a.clid = b.id
drop table #y,#r,#all
/*
材料                   需要数                                      成本                                       
-------------------- ---------------------------------------- ---------------------------------------- 
16镍铁合金               23.376620                                233.766200
*/go
drop table ys,cl,clcf,cp,cpcf
go 

Answer 3

你的问题分为两步：
第一步：解方程式（由于看题失误，12L的算法并没有给出计算方程式的解）
材料C1 有 C1YS1(元素1在材料1中的含量),C1YS2(元素2在材料1中的含量),C1YS3,...,C1YSN(元素N在材料1中的含量)
材料C2 有 B1,B2,B3,...,BN
....
材料CN 有 CNYS1,CNYS2,CNYS3,...,CNYSN(元素N在材料N中的含量)产品CP1 有CP1YS1,CP1YS1,CP1YS3,...,CPNYSN，给出ZL，
如果最小单位为：顿 ZL = 20 公斤 ZL = 20*1000 克 ZL = 20*1000*1000 毫克 ZL = 20*1000*1000*1000
在上述给定的精度范围求解方程式组（未知量均为整数）：
PS:对于杂质，不加入到计算元素中，也就是在上述元素中不包含杂质元素。ZL*CP1YS1 = X1*(C1YS1+C2YS1+...+CNYS1)
ZL*CP1YS2 = X2*(C1YS2+C2YS2+...+CNYS2)
...
ZL*CP1YSN = XN*(C1YSN+C2YSN+...+CNYSN)
对于给定的一组数据，可能无解，也可能唯一解，也可能是解集合。
对于无解和唯一解，问题到此结束，给出答案就行。
对于解集合就要进入第二步。
第二步：求最优解
这是一个典型的N-P完全问题，除了用枚举算法外，其它算法无法求得最优解。
目前常用的算法是贪心算法，贪心算法能给出一个接近解，但不是最优解，并且在极端情况下可能是最差解，我在12L给出的基于最大数量需求的最低价格的贪心算法，当然，为了避免求得最差解，一般采用多种贪心算法，最后比较各种贪心算法中的最好解作为最终的解。

Answer 4

还有就是这种题目放在SQL中显然不是最好的处理方式，因为要大量用到数组和递归，因此放在中间业务层处理比较理想，关于进一步的算法实现，可以到算法论坛提问。

Answer 5

13L的方程式写错了应该是：
ZL*CP1YS1 = X1*C1YS1+X2*C2YS1+...+XN*CNYS1
ZL*CP1YS2 = X1*C1YS2+X2*C2YS2+...+XN*CNYS2
... 
ZL*CP1YSN = X1*C1YSN+X2*C2YSN+...+XN*CNYSN

Answer 6

求解方程式的算法可以参照下面的22L：
数据准备：
--求CNSYN 放在#cnsyn 中(clid材料编号 int,cfid 元素编号,csy int 材料元素含量,cpsy 产品元素含量 int),精度为公斤，ZL=20000
select a.clid,a.cfid,isnull(a.hl,0),isnull(b.hl,0)*200 into #cnsyn 
from clcf a full join cpcf b on a.cfid = b.cfid where   isnull(a.hl,0) <> = 0 or  isnull(b.hl,0) <> 0
参考方法：
http://topic.csdn.net/u/20071227/08/4f5d9279-2e70-4a66-82ae-ab46dba5769c.html

Answer 7

给出例子数据，方便大家交流
--元素(ys) 元素编号(id) 元素符号(fh) 元素名称(mc) 元素标志(bz)
create table ys(id int,fh varchar(10),mc varchar(20),bz varchar(10))
insert ys select 1,'Cu','铜',''
union all select 2,'Nr','镍','' 
union all select 3,'Mn','锰',''
union all select 4,'Fe','铁','' 
union all select 5,'C','炭','杂质'--材料(cl) 材料编号(id) 材料名称(mc) 材料单价(jg)
create table cl(id int,mc varchar(20),jg int)
insert cl select 1,'16镍铁合金',18000
union all select 2,'10镍铁合金',10000
union all select 3,'12镍铁合金',12000 
union all select 4,'电解Cu（纯铜)',16000 
union all select 5,'废铁（纯铁）',6000
--材料成分(clcf) 材料编号(clid) 元素编号(cfid) 含量(hl)
create table clcf(clid int,cfid varchar(10),hl int)
insert clcf select 1,1,2   union select 1,2,16 union select 1,3,0 union select 1,4,77  union select 1,5,5
union  all  select 2,1,1   union select 2,2,10 union select 2,3,0 union select 2,4,83  union select 2,5,6
union  all  select 3,1,1   union select 3,2,12 union select 3,3,0 union select 3,4,82  union select 3,5,5
union  all  select 4,1,100 union select 4,2,0  union select 4,3,0 union select 4,4,0   union select 4,5,0
union  all  select 5,1,0   union select 5,2,0  union select 5,3,0 union select 5,4,100 union select 5,5,0
--产品(cp) 产品编号(id) 产品名称(mc)
create table cp(id int,mc varchar(20))
insert cp select 1,'201号铁'
--产品成分(cpcf) 产品编号(cpid) 元素编号(cfid) 含量(hl)
create table cpcf(cpid int,cfid int,hl int)
insert cpcf select 1,1,0 union select 1,2,8 union select 1,3,0 union select 1,4,90 union select 1,5,2
go
drop table ys,cl,clcf,cp,cpcf
go