p*****9
发帖数: 20 | 1 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
下。
题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
最小剩余空间，递归公式为：
opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
上时所剩余的总载重空间。
不知这样做对不对，有没有更简单的解法？谢谢！ | g*****a
发帖数: 12 | 2 用DP,matrix(i,j)表示第j条船上在放第i个箱子时候的载重。matrix(i,j)=Wi+matrix(
i-1,j). j 从0到m，包括不放在任何一条船上的情况。放完一个箱子，如果matrix(i,j
)>Cj for every j, 记录这时候的剩余空间。比较最后输出最小值。 | g*****a
发帖数: 12 | | P*******L
发帖数: 2637 | 4 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| g*****a
发帖数: 12 | 5 我猜应该是n个箱子不一定全部要放上去，能放多少放多少，哪样剩的空间最小
【在 P*******L 的大作中提到】
: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
| p*****9
发帖数: 20 | 6 sorry, 我题目没说明白。不一定所有的箱子都能装上去啊，会超重的。题目的意思是
，在每个船都不超重的情况下，尽可能装满。
【在 P*******L 的大作中提到】
: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
| r****7
发帖数: 2282 | 7 有m条船你只记一个j不够吧。
应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
jm)), opt(i - 1, j1, j2...jm))
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| p*****9
发帖数: 20 | 8 嗯，有道理。。。我靠，好复杂……
..
【在 r****7 的大作中提到】
: 有m条船你只记一个j不够吧。
: 应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
: jm)), opt(i - 1, j1, j2...jm))
| t*****l
发帖数: 241 | 9 maximum flow problem
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| d*****1
发帖数: 263 | 10 第一眼感觉是线性优化的题目。
用 simplex method。
每个Wi 重复出现m次就行。然后再给一个船，容量无限，但权重为0
-------但，这里我们得要 未知数为0，1的怎么去限制----------
-----------------求大牛们 拍醒---------- | | | M*******a
发帖数: 1633 | 11 不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。 | a******u
发帖数: 69 | | l*y
发帖数: 70 | 13 Brutal force DFS worst case scenario (m+1)^n 可以么 | f*****g
发帖数: 887 | 14 如果DFS的话，复杂度是m!个knapsack problem吧 | p*****9
发帖数: 20 | 15 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
下。
题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
最小剩余空间，递归公式为：
opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
上时所剩余的总载重空间。
不知这样做对不对，有没有更简单的解法？谢谢！ | g*****a
发帖数: 12 | 16 用DP,matrix(i,j)表示第j条船上在放第i个箱子时候的载重。matrix(i,j)=Wi+matrix(
i-1,j). j 从0到m，包括不放在任何一条船上的情况。放完一个箱子，如果matrix(i,j
)>Cj for every j, 记录这时候的剩余空间。比较最后输出最小值。 | g*****a
发帖数: 12 | | P*******L
发帖数: 2637 | 18 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| g*****a
发帖数: 12 | 19 我猜应该是n个箱子不一定全部要放上去，能放多少放多少，哪样剩的空间最小
【在 P*******L 的大作中提到】
: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
| p*****9
发帖数: 20 | 20 sorry, 我题目没说明白。不一定所有的箱子都能装上去啊，会超重的。题目的意思是
，在每个船都不超重的情况下，尽可能装满。
【在 P*******L 的大作中提到】
: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi
| | | r****7
发帖数: 2282 | 21 有m条船你只记一个j不够吧。
应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
jm)), opt(i - 1, j1, j2...jm))
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| p*****9
发帖数: 20 | 22 嗯，有道理。。。我靠，好复杂……
..
【在 r****7 的大作中提到】
: 有m条船你只记一个j不够吧。
: 应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
: jm)), opt(i - 1, j1, j2...jm))
| t*****l
发帖数: 241 | 23 maximum flow problem
【在 p*****9 的大作中提到】
: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！
| d*****1
发帖数: 263 | 24 第一眼感觉是线性优化的题目。
用 simplex method。
每个Wi 重复出现m次就行。然后再给一个船，容量无限，但权重为0
-------但，这里我们得要 未知数为0，1的怎么去限制----------
-----------------求大牛们 拍醒---------- | M*******a
发帖数: 1633 | 25 不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。 | a******u
发帖数: 69 | | l*y
发帖数: 70 | 27 Brutal force DFS worst case scenario (m+1)^n 可以么 | f*****g
发帖数: 887 | 28 如果DFS的话，复杂度是m!个knapsack problem吧 | c*****n
发帖数: 95 | 29 这道题确实很变态, multiple knapsack problem。今天刷topcoder 遇到一个类似问题
。可以学习一下。
http://community.topcoder.com/tc?module=Static&d1=match_editori
题目叫collectingmarbles.
需要保持的状态非常多。 | s**x
发帖数: 7506 | |
|
