g***x
发帖数: 494 | 1 有两个表分别有1024和2048个0到4000的数（不一定是整数），这两个表都是递增的。
并且表里的值都是已知的，两个表的第一个元素都是0，最后一个元素都是4000例如
table1[0]=0;table1[1]=0.5;table1[2]=1; table1[3]=2; ...... table1[1023]=4000
table2[0]=0;table2[1]=0.2;table2[2]=0.5;table2[3]=0.75;table2[4]=1.1; table2
[5]=2; ... table2[2047]=4000
现在的问题是如何从table2中挑选出1024个index使得这1024个值所组成的曲线和
table1的曲线最好地一致。
比如上面的例子中可从表2中挑选出第 0，2，4,5,... 2047个元素得到的数是：
0，0.5，1.1，2，... 4000这和表1的元素0,0.5,1,2,4000符合的很好。
请问可以用什么算法来实现，并且最快。 | t****a
发帖数: 1212 | 2 抛砖引玉：
DP, 复杂度O(n^3), n为第一个数组长度
1、设立表格Error: 2n x n，表格中每个单元(x, y)代表table1[1..y]与table2[1..x]
的比对最优解（误差平方和最小）.
2、最优解Error[2n, n] = Min (Error[2n-i, n-1] + (table1[n]-table2[2n]
)^2), in which 0 < i < n and i is int.
3. 记录最优解的路径
此解法可改进为O(n^2) | m*****g
发帖数: 226 | | h**k
发帖数: 3368 | 4 如果两条曲线最好的一致，是定义为sum( abs(table1[i] - table2[the i-th chose
element]) )最小么？
如果这样可以找到一个线性的算法。
同时开始扫描两个数组，对于table1中的每个值a，可以只需要计算table2中的两个值
与它的差，这两个值一个是最大的比a小的值，一个是最小的比a大的值。
4000
table2
【在 g***x 的大作中提到】
: 有两个表分别有1024和2048个0到4000的数（不一定是整数），这两个表都是递增的。
: 并且表里的值都是已知的，两个表的第一个元素都是0，最后一个元素都是4000例如
: table1[0]=0;table1[1]=0.5;table1[2]=1; table1[3]=2; ...... table1[1023]=4000
: table2[0]=0;table2[1]=0.2;table2[2]=0.5;table2[3]=0.75;table2[4]=1.1; table2
: [5]=2; ... table2[2047]=4000
: 现在的问题是如何从table2中挑选出1024个index使得这1024个值所组成的曲线和
: table1的曲线最好地一致。
: 比如上面的例子中可从表2中挑选出第 0，2，4,5,... 2047个元素得到的数是：
: 0，0.5，1.1，2，... 4000这和表1的元素0,0.5,1,2,4000符合的很好。
: 请问可以用什么算法来实现，并且最快。
| t****a
发帖数: 1212 | 5 这个方法在有些时候会失效的，因为没有考虑a的后一个元素和那两个值的关系。
【在 h**k 的大作中提到】
: 如果两条曲线最好的一致，是定义为sum( abs(table1[i] - table2[the i-th chose
: element]) )最小么？
: 如果这样可以找到一个线性的算法。
: 同时开始扫描两个数组，对于table1中的每个值a，可以只需要计算table2中的两个值
: 与它的差，这两个值一个是最大的比a小的值，一个是最小的比a大的值。
:
: 4000
: table2
| P***t
发帖数: 1006 | 6 Seems to be a DP problem.
define a function best(i, j) as the best minimal diff you could get to match
the array A[i, end] to B[j, end), then
best(i, j) = min (
(A[i]-B[j]) * (A[i] - B[j]) + best(i+1, j+1), // Use j to match i.
best(i, j+1) // Use some number after j to match i.
)
space/time complexity is O(A.size() * B.size()). |
|
