m*******a
发帖数: 24 | 1 题目大概是这个意思：
给定N个长度为L的Array，现在从这N个array中选择M个数，使这M个数的和最大。唯一
的限制是从任一个array中取数时，必须从第一个开始取，
依次取若干个(可以取任意多个array）
举例来说：
array 1: 3， 5， 4， 10
array 2: 2, 10, 6, 1
array 3: 7, 8, 1，10
如果M=3，那就是取第二个array的2，10 和第三个array的7。
明显应该是用dynamic programming，但感觉自己想的很复杂。大家有什么思路？多谢 | d****n
发帖数: 12461 | 2 无非就是f(m,n,p)=max{f(m-1,n,p)+a[m-1],f(m,n-1,p)+b[n-1],f(m,n,p-1)+c[p-1]}
然后设好初始条件就可以了。 | m*******a
发帖数: 24 | 3 可能是我没理解不对。你这种是只取一个array吗？可以取任意多个，但每个都必须从
开始取。
【在 d****n 的大作中提到】
: 无非就是f(m,n,p)=max{f(m-1,n,p)+a[m-1],f(m,n-1,p)+b[n-1],f(m,n,p-1)+c[p-1]}
: 然后设好初始条件就可以了。
| b***e
发帖数: 1419 | 4 你这个刚才不是排好序的吗？现在改了？
【在 m*******a 的大作中提到】
: 题目大概是这个意思：
: 给定N个长度为L的Array，现在从这N个array中选择M个数，使这M个数的和最大。唯一
: 的限制是从任一个array中取数时，必须从第一个开始取，
: 依次取若干个(可以取任意多个array）
: 举例来说：
: array 1: 3， 5， 4， 10
: array 2: 2, 10, 6, 1
: array 3: 7, 8, 1，10
: 如果M=3，那就是取第二个array的2，10 和第三个array的7。
: 明显应该是用dynamic programming，但感觉自己想的很复杂。大家有什么思路？多谢
| b***e
发帖数: 1419 | 5 复杂性O(M^N) at least。
【在 d****n 的大作中提到】
: 无非就是f(m,n,p)=max{f(m-1,n,p)+a[m-1],f(m,n-1,p)+b[n-1],f(m,n,p-1)+c[p-1]}
: 然后设好初始条件就可以了。
| m*******a
发帖数: 24 | 6 应该是不排序的。。。我开始弄错了。但感觉排序于否好像没什么影响
【在 b***e 的大作中提到】
: 你这个刚才不是排好序的吗？现在改了？
| b***e
发帖数: 1419 | 7 排序的话好做一万倍。
【在 m*******a 的大作中提到】
: 应该是不排序的。。。我开始弄错了。但感觉排序于否好像没什么影响
|
|
