请教一个算法问题(各位大DFW小弟这个问题出一千分,只要谁能给出正确而且说明详细的算法) (100分)

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-11

• #1

有N种同类原料都含铝含铝量分别是L1、L2、L3...Ln，重量不定分别W1、W2、W3...Wn（Wi>=0），其价格也随含铝量
变化分别是P1、P2、P3....Pn（Pi>0），现在根据生产的需要要混合原料，达到指定含铝量的加工材料（简单的机械混合），
现在请教算法：要得到一定重量(W)、一定含铝量（L）的加工材料，原料价格最低。
(可以限顶n<=10)
小弟实在没有时间细细推敲各位DFW的算法,只要给出正确而又详细的算法分分马上给出,(请管理员监督)
小弟的email是 wayne_han@163.com
(6月26日对题目再做修改)

 

W

wp_hammer

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-11

• #2

首先我们能确定所需原料(L)是由两种原料组成的。我们假设两种原料是Li和Lj,
并且Li<=L<=Lj，需要Li的重量是Wi，需要Lj的重量是(W-Wi)，W是L的重量。
那麽，L*M=Li*Wi+Lj*(W-Wi)
所以，Wi=(Lj-L)*W/(Lj-Li)
原料的价格是 Pi*Wi+Pj*(W-Wi)
写程序把大于等于L的和小于等于L的分开，做所有的可能组合的到最小的。
注：符合要求的原料是两种组成的，可以证明（略）

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-11

• #3

假设我要得到含铝45%的100KG，原料有15%的单价1共有20KG、20%的单价100有200KG、50%的单价300有200KG。那么我的原料自然不会是两种，而是三种。

 

W

wp_hammer

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-11

• #4

你是说某种原料可能不足，是吗？
用你所举15%20KG需要50%120KG,一共得到45%140KG
剩下45%60KG,用20%和50%组成（也就是第二好的方案或者是并列第一好得更好）

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-12

• #5

是的，某些原料有可能不足。
各位大哥帮帮忙，分数不够可以加。
自己UP一下

 

W

wp_hammer

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-12

• #6

老兄，我说的方法不行吗？
你把理论上的可能组合价格算出，（用两种原料配）排好序
如：（L1,L4）P1，（L1,L6）P2........
价格P1<=P2<=P3<=........<=Px
你先用P1的组合，如果不够再用P2的组合补上余下的，不够再用P3.........
这样就行了，把两两组合的算法做好，没问题的。

 

刘

刘李子

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-12

• #7

gz

 

鲨

鲨鱼

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-12

• #8

如果含铝量与价格成正比应该比较好解决

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-13

• #9

各位DFW快来看看我的题目，再加200分。
如果原料只有10种呢。
自己UP一下

 

K

Kinki

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-13

• #10

我看把原料按照L分为两组L1-Li和Li+1-Ln(Li<L,Li+1>L)
然后做。。。。[][]

 

D

dearmite

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-13

• #11

这一寻优问题呀，
EASY的，贪婪法，（以最大的目标（此题为含铝）先取，）
好的，回朔法（不要就换）
程序好写的，穷举呗（我不信你有无穷多的东西）
（）里的是这个算法的说明，
哈哈

 

L

linsb

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-13

• #12

1.求重量为w的组合
2.其中铝量为L的组合
3.其中价格最低的组合
思路对否？是否有解？

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-15

• #13

to:dearmite兄，能说的明白点吗？

请大家帮忙解一下这个题目，哥们还有900分，谁能给出正确详细的算法，全部分数一并给出。
自己UP一下

 

L

linsb

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-15

• #14

to hts
我给你的思路怎么不表态？如果可行，我担心的是是否有解？

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-15

• #15

to:linsb兄，你能说的详细点吗。
这个题目肯定有解的，因为题目本身就是一个公司实际生产的一个过程，而且老资格的技术员有一个口诀式的算法（可惜我不知道：（）

 

L

linsb

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-06-15

• #16

对于你的具体资料不十分清楚，如n为多少？
按我给你的思路，就是一个穷举法。列出所有可能，逐级缩小范围，如果集合不为空
价格最低的组合的为解，否则无解。这里的w和l为一固定数，很难求解，如果一定要
有解，对w和l要修正，直至得解。
在运筹学有线性规划模型，很成熟，你的问题是否可化为线性规划？
目标函数： Z=p1*L1+p2*L2+....pn*Ln
求Z为最小
其约束条件为
Li>=0 (i=1,2,....n)
其他详情不知不好确定
其形式为：
a1*L1+....an*Ln>=bi
........

 

L

lj.ah

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-03

• #17

我想这就是一个线形规划的问题。
N种原料混合，每种原料的重量各是多少时，混合后原料的价格Z最低。
目标函数： Z＝(W1/W)*P1+(W2/W)*P2+...+(Wn/W)*Pn (Pn为各种原料的单价)
约束条件：W＝W1+W2+...+Wn
L=L1*W1+L2*W2+...+Ln*Wn
W1>=0,W2>=0,...Wn>=0
其中L1,L2...Ln,P1,P2...Pn,W,L已知。

可以用单纯行法解此问题。这个具体程序嘛，^_^我只有fortran的，如果需要我贴出来，
哪位高手再译成pascal？

 

R

real_clq

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-07-03

• #18

可惜看不懂,好多分哪！

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-05

• #19

挂了好久了，不好意思，结了吧

 

H

hts

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-04-16

• #20

多人接受答案了。