a***y
发帖数: 13 | 1 有n 碓物质， 每碓物质都包含3种成分A,B和C，每碓A,B,C百分比不同, 现用一卡车拉
这n碓物质，卡车最多能拉B的量和C的量是固定的，目标是卡车拉尽可能多的A成分，求
算法。 |
E*****m
发帖数: 25615 | 2 每堆重量不同嗎？
題意不太清楚。
應該是 Knapsack problem 的變異。 |
a***y
发帖数: 13 | 3 多谢，每碓重量不同， 求卡车拉的每种物质所占百分比
【在 E*****m 的大作中提到】
: 每堆重量不同嗎？
: 題意不太清楚。
: 應該是 Knapsack problem 的變異。
|
g*****g
发帖数: 34805 | 4 如果每堆你不能挑着拿，难道不是算个最多拿多少B, C没超标，总量没超标。
每堆算一次取个A最大就完了。O(N)
【在 a***y 的大作中提到】
: 多谢，每碓重量不同， 求卡车拉的每种物质所占百分比
|
s*w
发帖数: 729 | 5 constrained optimization
to maximize A*X while B*X<=b and C*X<=c【 在 alady (alady) 的大作中提到: 】 |
a***y
发帖数: 13 | 6 can you please point me the implemented algorithm?
【在 s*w 的大作中提到】
: constrained optimization
: to maximize A*X while B*X<=b and C*X<=c【 在 alady (alady) 的大作中提到: 】
|
s*w
发帖数: 729 | 7 如果你就是要结果的话，推荐用现成的 package, 比如 matlab 的 optimization tool
box, 或者 c++ 的 gecode 库
自己写的话，貌似不是很容易，考虑到 xi 是浮点数; 得看看那些基本的解法，比如 s
implex, interior-point, 不过很多介绍都是大概念，没足够的细节；找一个好的面向
implementation 的教材不容易。
xi 要是 integer 的话，小问题可以直接 穷举; 大问题也许可以用 dp, 很像 knapsac
k, 我没想清楚怎么用
【在 a***y 的大作中提到】
: can you please point me the implemented algorithm?
|
E*****m
发帖数: 25615 | 8
這題目跟Knapsack 是等價的， NP-hard！
http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple
你來個 greedy O(N) 算你狠！ 八成是題目沒看懂。
【在 g*****g 的大作中提到】
: 如果每堆你不能挑着拿，难道不是算个最多拿多少B, C没超标，总量没超标。
: 每堆算一次取个A最大就完了。O(N)
|
z****e
发帖数: 54598 | 9 你认识有做运筹学的老师么？
operation research
这种问题找他们最好
【在 a***y 的大作中提到】
: 有n 碓物质， 每碓物质都包含3种成分A,B和C，每碓A,B,C百分比不同, 现用一卡车拉
: 这n碓物质，卡车最多能拉B的量和C的量是固定的，目标是卡车拉尽可能多的A成分，求
: 算法。
|
c********p
发帖数: 1969 | 10 哈哈我当年去旁听or的课一看太简单了就被偶b4了。。。
【在 z****e 的大作中提到】
: 你认识有做运筹学的老师么？
: operation research
: 这种问题找他们最好
|
z****e
发帖数: 54598 | 11 经济类的课程多数都不是很难
深入了后自然会很难
【在 c********p 的大作中提到】
: 哈哈我当年去旁听or的课一看太简单了就被偶b4了。。。
|
c********p
发帖数: 1969 | 12 IE的课。
【在 z****e 的大作中提到】
: 经济类的课程多数都不是很难
: 深入了后自然会很难
|
