b*******2
发帖数: 2121 | 1 A公司要ship 总共 n bottles of products，
有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
对应的盒子cost 分别是c1,c2,c3...cm.
盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
怎么选择一种盒子的combination 可以使花费最少？
我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
在一下转不过弯来，这个要怎么做。
希望大侠指导！
万分感谢！ |
H*******g
发帖数: 1477 | 2 应该是m种盒子吧
【在 b*******2 的大作中提到】
: A公司要ship 总共 n bottles of products，
: 有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
: 对应的盒子cost 分别是c1,c2,c3...cm.
: 盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
: 怎么选择一种盒子的combination 可以使花费最少？
: 我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
: 在一下转不过弯来，这个要怎么做。
: 希望大侠指导！
: 万分感谢！
|
H*******g
发帖数: 1477 | 3 把盒子的cost除以它能装的bottle数，然后按这个类似于“单价”的数据给盒子排序
然后，在给定bottle总数n个的前提下，用除余数的方法，尽量先多用单价便宜的盒子
装，剩下的bottle数再类似处理，直至bottle被装完.
请大侠来鉴定一下这样对不对啊？具体的应该怎么写？谢谢 |
w***g
发帖数: 5958 | 4
线性规划问题，没法用动态规划写。
。
【在 b*******2 的大作中提到】
: A公司要ship 总共 n bottles of products，
: 有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
: 对应的盒子cost 分别是c1,c2,c3...cm.
: 盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
: 怎么选择一种盒子的combination 可以使花费最少？
: 我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
: 在一下转不过弯来，这个要怎么做。
: 希望大侠指导！
: 万分感谢！
|
H*******g
发帖数: 1477 | 5 线性规划应该怎么写呀？和动态有啥区别？
怎么判断是线性的还是动态的？
【在 w***g 的大作中提到】
:
: 线性规划问题，没法用动态规划写。
: 。
|
r*******n
发帖数: 3020 | 6 typedef struct {
float price;
int n;
} node;
node a[m];
for(int i=0; i
a[i].price=ci/mi;
a[i].quantity=mi;
}
sort the array of a[...] decreasingly.
for(int i=0; i
int t=N/a[i].quantity;
if(t == 0 )
continue;
else{
N = N - t*a[i].quantity;
printf("%d\t", i);
}
}
【在 H*******g 的大作中提到】
: 把盒子的cost除以它能装的bottle数，然后按这个类似于“单价”的数据给盒子排序
: 然后，在给定bottle总数n个的前提下，用除余数的方法，尽量先多用单价便宜的盒子
: 装，剩下的bottle数再类似处理，直至bottle被装完.
: 请大侠来鉴定一下这样对不对啊？具体的应该怎么写？谢谢
|
i******t
发帖数: 370 | 7 可以用DP写的.
令C(n)=minimal cost。
C(n)=min(C(n-x1)+c1,C(n-x2)+c2,...,C(n-xk)+ck)
C(m)=0 for m<=0.
LP可以解，不过得到的是fractional solution，rounding不能保证最优
【在 w***g 的大作中提到】
:
: 线性规划问题，没法用动态规划写。
: 。
|
r*****e
发帖数: 7853 | 8 Integer programming:
min(c1*n1+...+cm*nm)
such that x1*n1+...+xm*nm=n; ni>=0; ni are integers
【在 b*******2 的大作中提到】
: A公司要ship 总共 n bottles of products，
: 有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
: 对应的盒子cost 分别是c1,c2,c3...cm.
: 盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
: 怎么选择一种盒子的combination 可以使花费最少？
: 我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
: 在一下转不过弯来，这个要怎么做。
: 希望大侠指导！
: 万分感谢！
|
r*****e
发帖数: 7853 | 9 Take a loot at: http://en.wikipedia.org/wiki/Knapsack_problem
It's an NP-complete problem.
【在 b*******2 的大作中提到】
: A公司要ship 总共 n bottles of products，
: 有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
: 对应的盒子cost 分别是c1,c2,c3...cm.
: 盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
: 怎么选择一种盒子的combination 可以使花费最少？
: 我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
: 在一下转不过弯来，这个要怎么做。
: 希望大侠指导！
: 万分感谢！
|
s*****g
发帖数: 5159 | 10 General assignment problem.
NP hard.
No polynomial time algorithm can solve that within approximation ratio of 1.
5 (in terms of total cost).
There is a 2 approximation polynomial algorithm.
Check Shmoy and Tados 87, and another paper by Shmoy Tados and another guy i
n 1993.
If this is an interview question, you could tell the interviewer forget abou
t it.
【在 b*******2 的大作中提到】
: A公司要ship 总共 n bottles of products，
: 有m个不同的盒子可以用来装载，每个盒子分别可以装x1,x2,x3... xm 个bottles，
: 对应的盒子cost 分别是c1,c2,c3...cm.
: 盒子和对应的cost没有任何联系，每种盒子可以选择一个或多个或不选择。
: 怎么选择一种盒子的combination 可以使花费最少？
: 我记得以前做过类似的题目，有一点不同，就是每个盒子只能选择一个或者不选择。现
: 在一下转不过弯来，这个要怎么做。
: 希望大侠指导！
: 万分感谢！
|
|
|
l******e
发帖数: 470 | 11 应该不是generalized assignment problem
感觉lz的意思物品是无差别的，就箱子有差别
前几楼的dynamic program肯定是对的，就是伪多项式
每个箱子可以用多次，感觉都不象nphard，当然只是感觉。
1.
i
abou
【在 s*****g 的大作中提到】
: General assignment problem.
: NP hard.
: No polynomial time algorithm can solve that within approximation ratio of 1.
: 5 (in terms of total cost).
: There is a 2 approximation polynomial algorithm.
: Check Shmoy and Tados 87, and another paper by Shmoy Tados and another guy i
: n 1993.
: If this is an interview question, you could tell the interviewer forget abou
: t it.
|
i******t
发帖数: 370 | 12 Guys, you are confused. The number of bottles are integers - this is a
knapsack with integer price/cost. For this problem DP suffices. For the
general problem, you still can use DP to get a pseudo-polynomial algorithm.
1.
i
abou
【在 s*****g 的大作中提到】
: General assignment problem.
: NP hard.
: No polynomial time algorithm can solve that within approximation ratio of 1.
: 5 (in terms of total cost).
: There is a 2 approximation polynomial algorithm.
: Check Shmoy and Tados 87, and another paper by Shmoy Tados and another guy i
: n 1993.
: If this is an interview question, you could tell the interviewer forget abou
: t it.
|
i******t
发帖数: 370 | 13 不是伪，就是多项式
【在 l******e 的大作中提到】
: 应该不是generalized assignment problem
: 感觉lz的意思物品是无差别的，就箱子有差别
: 前几楼的dynamic program肯定是对的，就是伪多项式
: 每个箱子可以用多次，感觉都不象nphard，当然只是感觉。
:
: 1.
: i
: abou
|
l******e
发帖数: 470 | 14 伪不伪的问题这个版至少都讨论过10次
【在 i******t 的大作中提到】
: 不是伪，就是多项式
|
i******t
发帖数: 370 | 15 鉴于大家都不会翻旧章，每个话题都会被讨论至少10次的，呵呵
【在 l******e 的大作中提到】
: 伪不伪的问题这个版至少都讨论过10次
|
l******e
发帖数: 470 | 16 想了下，是nphard的
让ci=mi
就是subset sum，但是每个数可以取多次
把gareyjohnson上subsetsum的证明改改就有了。
【在 l******e 的大作中提到】
: 应该不是generalized assignment problem
: 感觉lz的意思物品是无差别的，就箱子有差别
: 前几楼的dynamic program肯定是对的，就是伪多项式
: 每个箱子可以用多次，感觉都不象nphard，当然只是感觉。
:
: 1.
: i
: abou
|
i******t
发帖数: 370 | 17 刚想说这不是subset sum。optimal的时候箱子不一定是满的，所以不是sum...
【在 l******e 的大作中提到】
: 想了下，是nphard的
: 让ci=mi
: 就是subset sum，但是每个数可以取多次
: 把gareyjohnson上subsetsum的证明改改就有了。
|
l******e
发帖数: 470 | 18 从subset sum规约过来，可以了吧
【在 i******t 的大作中提到】
: 刚想说这不是subset sum。optimal的时候箱子不一定是满的，所以不是sum...
|
b*******2
发帖数: 2121 | 19 怎么感觉像greedy？
【在 H*******g 的大作中提到】
: 把盒子的cost除以它能装的bottle数，然后按这个类似于“单价”的数据给盒子排序
: 然后，在给定bottle总数n个的前提下，用除余数的方法，尽量先多用单价便宜的盒子
: 装，剩下的bottle数再类似处理，直至bottle被装完.
: 请大侠来鉴定一下这样对不对啊？具体的应该怎么写？谢谢
|
b*******2
发帖数: 2121 | 20 多谢指导。
这是课堂上的问题，一个take home quiz。老师指名说是Dynamic programming. 我们
课上还没讲NP, 应该不是NP...
或者是老师题目有问题？或许是我理解题目有问题？ = =!!
1.
i
abou
【在 s*****g 的大作中提到】
: General assignment problem.
: NP hard.
: No polynomial time algorithm can solve that within approximation ratio of 1.
: 5 (in terms of total cost).
: There is a 2 approximation polynomial algorithm.
: Check Shmoy and Tados 87, and another paper by Shmoy Tados and another guy i
: n 1993.
: If this is an interview question, you could tell the interviewer forget abou
: t it.
|
|
|
b*******2
发帖数: 2121 | 21 非常感谢！
不过老师指明是dynamic programming。
莫非我题目理解错误？
【在 r*****e 的大作中提到】
: Take a loot at: http://en.wikipedia.org/wiki/Knapsack_problem
: It's an NP-complete problem.
|
b*******2
发帖数: 2121 | 22 恩，
非常感谢！
【在 i******t 的大作中提到】
: 可以用DP写的.
: 令C(n)=minimal cost。
: C(n)=min(C(n-x1)+c1,C(n-x2)+c2,...,C(n-xk)+ck)
: C(m)=0 for m<=0.
: LP可以解，不过得到的是fractional solution，rounding不能保证最优
|
p*******r
发帖数: 475 | 23 DP做出来的不保证是多项式时间
【在 b*******2 的大作中提到】
: 多谢指导。
: 这是课堂上的问题，一个take home quiz。老师指名说是Dynamic programming. 我们
: 课上还没讲NP, 应该不是NP...
: 或者是老师题目有问题？或许是我理解题目有问题？ = =!!
:
: 1.
: i
: abou
|
w***g
发帖数: 5958 | 24 正解。
【在 p*******r 的大作中提到】
: DP做出来的不保证是多项式时间
|
H*******g
发帖数: 1477 | 25 伪不伪有什么区别啊？
【在 l******e 的大作中提到】
: 伪不伪的问题这个版至少都讨论过10次
|
H*******g
发帖数: 1477 | 26 不满的箱子应该尽可能少吧？是为了满足rounding吗？
【在 i******t 的大作中提到】
: 刚想说这不是subset sum。optimal的时候箱子不一定是满的，所以不是sum...
|
l******e
发帖数: 470 | |
b********o
发帖数: 466 | |
r*****e
发帖数: 7853 | 29 Also DP cannot guarantee global optimum, like the Viterbi algorithm
【在 p*******r 的大作中提到】
: DP做出来的不保证是多项式时间
|
