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

  • 主题发起人 主题发起人 hts
  • 开始时间 开始时间
H

hts

Unregistered / Unconfirmed
GUEST, unregistred user!
有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日对题目再做修改)
 
首先我们能确定所需原料(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的分开，做所有的可能组合的到最小的。
注：符合要求的原料是两种组成的，可以证明（略）
 
假设我要得到含铝45%的100KG，原料有15%的单价1共有20KG、20%的单价100有200KG、50%的单价300有200KG。那么我的原料自然不会是两种，而是三种。
 
你是说某种原料可能不足，是吗？
用你所举15%20KG需要50%120KG,一共得到45%140KG
剩下45%60KG,用20%和50%组成（也就是第二好的方案或者是并列第一好得更好）
 
是的，某些原料有可能不足。
各位大哥帮帮忙，分数不够可以加。
自己UP一下
 
老兄，我说的方法不行吗？
你把理论上的可能组合价格算出，（用两种原料配）排好序
如：（L1,L4）P1，（L1,L6）P2........
价格P1<=P2<=P3<=........<=Px
你先用P1的组合，如果不够再用P2的组合补上余下的，不够再用P3.........
这样就行了，把两两组合的算法做好，没问题的。
 
如果含铝量与价格成正比应该比较好解决
 
各位DFW快来看看我的题目，再加200分。
如果原料只有10种呢。
自己UP一下
 
我看把原料按照L分为两组L1-Li和Li+1-Ln(Li<L,Li+1>L)
然后做。。。。[:D][:D]
 
这一寻优问题呀，
EASY的，贪婪法，（以最大的目标（此题为含铝）先取，）
好的，回朔法（不要就换）
程序好写的，穷举呗（我不信你有无穷多的东西）
（）里的是这个算法的说明，
哈哈
 
1.求重量为w的组合
2.其中铝量为L的组合
3.其中价格最低的组合
思路对否？是否有解？
 
to:dearmite兄，能说的明白点吗？

请大家帮忙解一下这个题目，哥们还有900分，谁能给出正确详细的算法，全部分数一并给出。
自己UP一下
 
to hts
我给你的思路怎么不表态？如果可行，我担心的是是否有解？
 
to:linsb兄，你能说的详细点吗。
这个题目肯定有解的，因为题目本身就是一个公司实际生产的一个过程，而且老资格的技术员有一个口诀式的算法（可惜我不知道：（）
 
对于你的具体资料不十分清楚，如n为多少？
按我给你的思路，就是一个穷举法。列出所有可能，逐级缩小范围，如果集合不为空
价格最低的组合的为解，否则无解。这里的w和l为一固定数，很难求解，如果一定要
有解，对w和l要修正，直至得解。
在运筹学有线性规划模型，很成熟，你的问题是否可化为线性规划？
目标函数： Z=p1*L1+p2*L2+....pn*Ln
求Z为最小
其约束条件为
Li>=0 (i=1,2,....n)
其他详情不知不好确定
其形式为：
a1*L1+....an*Ln>=bi
........
 
我想这就是一个线形规划的问题。
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？
 
可惜看不懂,好多分哪！
 
挂了好久了，不好意思，结了吧
 
多人接受答案了。
 
您必须登录或注册才可回复。

Similar threads

Y
辞职，散分！！！(带个SQL问题，可不回答，灌水有分) (200分)
2 3
回复
52
查看
650
ysai
Y
Y
求一个 矩形最优化切割的 算法,200分(200分)
2
回复
21
查看
1K
LeeChange
L
H
那位大侠能用一个例子详细给小弟讲解一下Lotus Notes的邮件服务器的配置方法（带域名）。我是个新手，急用！！！万分感谢！(100分)
回复
1
查看
117
axcom
A
蒸
一个仓库流量计算的问题--大家看看吧(50分)
回复
1
查看
118
ww1234ww
W
B
求图象缩小（只需要缩小）尽量少失真的算法或代码，给点建议也行。(30分)
回复
15
查看
201
mjuyhn
M
后退
顶部