主题:这种类似于背包的题 如何回溯?
youthchen
[专家分:100] 发布于 2007-11-25 14:30:00
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设Wij是从供应商j处购得的第i个部件的重量, Cij是相应的价格。设计一个回溯的算法,使得总价格不超过C且机器重量最小。
回复列表 (共4个回复)
沙发
justforfun626 [专家分:18460] 发布于 2007-11-26 02:09:00
懒惰学生作业帖或变相作业帖一些共同特徵:
1。原封不动复制老师作业题
2。没有自己的思考
3。没有具体到点子上的问题,象我什么地方不懂
4。没有自己的解决方案和那里遇到了困难
5。要求源代码
6。紧急无比,但过期作废。你回答他(她)也不理你了
7。典型老师作业题目,多数见过。但是懒惰学生连搜索都懒得做
8。加上一些花样,企图冒充项目问题。虽然懒惰,还是比较好一些。因为至少转了两下脑筋
http://bbs.chinajavaworld.com/thread.jspa?threadID=726764&tstart=0
板凳
youthchen [专家分:100] 发布于 2007-11-30 11:02:00
呵呵 主要是想摆上来讨论下
要知道不是每个人都可以把题中的n个for循环用递归写成的
有些人在不知道的情况下
for()
for()
for()
for()
... // n个for循环
这样的穷举出现得不应该吧
是我问的时候疏忽了 我本以为大家能理解主要讨论些什么了
因为都说了是这种类背包题了
可能很久没来这里 不熟悉这里的情况
可能和我平时的讨论有关
我们拿出一道题的时候大家基本是能朝着一个方向了
3 楼
justforfun626 [专家分:18460] 发布于 2007-11-30 11:15:00
Here is a very good tutorial
[url=http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html]A Tutorial on Dynamic Programming[/url]
Knapsack Problem is included, Backward Recursion is expained in detail.
Take a look!
4 楼
youthchen [专家分:100] 发布于 2007-11-30 11:25:00
well i will read
thanks
and i know the dynamic programming is better to sovol the problem
but as a student we should learn not only one method
even the other methods are not the best
they will be the best to another problem
and finding more solution to the same problem is interesting
and helpful to your study
我来回复