R*****i
发帖数: 2126 | 1 输入是一些不同种类的产品，每一类有若干个，现有N个工人，每个工人都可以生产任
何一种产品，但付出的代价是不一样的，每一种具体分配情况都可以求出一个目标函数
（这个目标函数比较复杂，但根据具体分配情况可以快速求出），现在要想算出最佳分
配，使得目标函数最大。这种优化该怎么算？产品可以有一两百个，工人可能会有七八
个到
十来个。 |
T*******e
发帖数: 4928 | 2 没细看。感觉是背包。
【在 R*****i 的大作中提到】
: 输入是一些不同种类的产品，每一类有若干个，现有N个工人，每个工人都可以生产任
: 何一种产品，但付出的代价是不一样的，每一种具体分配情况都可以求出一个目标函数
: （这个目标函数比较复杂，但根据具体分配情况可以快速求出），现在要想算出最佳分
: 配，使得目标函数最大。这种优化该怎么算？产品可以有一两百个，工人可能会有七八
: 个到
: 十来个。
|
s*a
发帖数: 267 | |
R*****i
发帖数: 2126 | 4 给点具体办法啊。我农民，文化低，太高深我听不懂。 |
c********t
发帖数: 5706 | 5 生产优化应该是求代价最小吧？
按你说的这些条件，那就每件产品都找生产效率最高的那个工人做就好了。是不是还有
什么其他条件？
【在 R*****i 的大作中提到】
: 输入是一些不同种类的产品，每一类有若干个，现有N个工人，每个工人都可以生产任
: 何一种产品，但付出的代价是不一样的，每一种具体分配情况都可以求出一个目标函数
: （这个目标函数比较复杂，但根据具体分配情况可以快速求出），现在要想算出最佳分
: 配，使得目标函数最大。这种优化该怎么算？产品可以有一两百个，工人可能会有七八
: 个到
: 十来个。
|
R*****i
发帖数: 2126 | 6
不是这样滴。各人的生产效率要看分配的具体情况和其他人的分配情况（需要配合嘛）
，总之，目标函数是比较复杂的，但只要分配一定，目标立马能算出来。我优化问题也
知道一些，但这种问题不大熟。目前自己设计了一个算法，效果还可以，但很难算到真
正的最优解。
【在 c********t 的大作中提到】
: 生产优化应该是求代价最小吧？
: 按你说的这些条件，那就每件产品都找生产效率最高的那个工人做就好了。是不是还有
: 什么其他条件？
|
c********t
发帖数: 5706 | 7 听上去挺有意思的，能分享一下你的解决方法吗，如果能给个小李子就更好了，是用的
类似背包的DP吗？ |
R*****i
发帖数: 2126 | 8
我的方法是笨办法，类似与蒙特卡洛那样的随机选择，我对背包问题没有任何概念，目
前在leetcode上刷题，也许会遇到背包问题，到时候学一下。我是用JavaScript刷的，
JavaScript版的Leetcode解答好像并不多见，我把我的代码和体会都搁在华人IT网上了
（huaren-it.com )，希望能得到批评指正。
【在 c********t 的大作中提到】
: 听上去挺有意思的，能分享一下你的解决方法吗，如果能给个小李子就更好了，是用的
: 类似背包的DP吗？
|
R*****i
发帖数: 2126 | 9 看了一下背包问题，感觉跟分配优化问题相差甚远。背包是只有两个状态，放还是不放
。而分配优化问题可能有八九十来个状态，每个产品必须分配给八九十来个工人中的一
个。 |
h*****u
发帖数: 109 | 10 Parallel machine problems without preemption
复杂度依赖于具体情况，目标函数，有没有最大时间等
http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/pqr_nop/pqr_nop.pdf
面试会考这类问题？属于运筹学里的一个小领域了。 |
