题：
存在N个双值的向量V.其中向量的第i个索引处的值等于1/2 ^(i 1).例如：1 / 2,1 / 4,1 / 8,1 / 16等……
你要编写一个函数,它将一个双“r”作为输入,其中0< r< 1,并将V的索引输出到stdout,当求和时,将给出最接近值'r'的值,而不是来自向量V的任何其他索引组合. 此外,索引的数量应该是最小的,并且在有两个解决方案的情况下,应该优选最接近零的解.
void getIndexes(std::vector<double>& V,double r)
{
....
}
int main()
{
std::vector<double> V;
// populate V...
double r = 0.3;
getIndexes(V,r);
return 0;
}
注意：似乎有一些SO’er没有完全阅读这个问题的心情.所以请大家注意以下几点：
>解决方案,也就是总和可能大于r – 因此任何策略从r逐步减去分数,直到它达到零或接近零是错误的
>有r的例子,其中有2个解,即| r-s0 | == | r-s1 |和s0< s1 - 在这种情况下应该选择s0,这使问题稍微困难一些,因为背包式解决方案往往首先贪婪高估.
>如果您认为这个问题很简单,那么您很可能还没有理解它.因此,再次阅读这个问题是个好主意.
编辑(Matthieu M.)：V = {1 / 2,1 / 16,1 / 32}的2个例子
> r = 0.3,S = {1,3}
> r = 0.256652,S = {1}
解决方法
考虑目标数r和分数{1 / 2,…… 1 /(2 ^ N)}的集合F.令最小分数1 /(2 ^ N)表示为P.
那么最优总和将等于：
S = P * round(r/P)
也就是说,最佳和S将是可用的最小分数P的某个整数倍.最大误差err = r-S是±1/2 * 1 /(2 ^ N).没有更好的解决方案是可能的,因为这将需要使用小于1 /(2 ^ N)的数字,这是集合F中的最小数字.
由于分数F都是P = 1 /(2 ^ N)的两倍幂,P的任何整数倍可以表示为F中分数的总和.获得应该使用的分数列表,以二进制编码整数轮(r / P),并在第k个二进制位读出1“包括解决方案中的第k个分数”.
例：
Take
r = 0.3andFas{1/2,1/4,1/8,1/16,1/32}.
>将整个问题乘以32.
Take
r = 9.6,andFas{16,8,4,2,1}.
>将r舍入到最接近的整数.
Take
r = 10.
>将10编码为二进制整数(五位)
10 = 0b 0 1 0 1 0 ( 8 + 2 )
^ ^ ^ ^ ^
| | | | |
| | | | 1
| | | 2
| | 4
| 8
16
>将每个二进制位与分数相关联.
= 0b 0 1 0 1 0 ( 1/4 + 1/16 = 0.3125 )
^ ^ ^ ^ ^
| | | | |
| | | | 1/32
| | | 1/16
| | 1/8
| 1/4
1/2
证明
考虑通过将所涉及的所有数字乘以2 ** N来转换问题,以便所有分数变为整数.
原来的问题：
Consider a target number
rin the range0 < r < 1,and a list of fractions{1/2,.... 1/(2**N). Find the subset of the list of fractions that sums toSsuch thaterror = r - Sis minimised.
成为以下等效问题(乘以2 ** N后)：
Consider a target number
rin the range0 < r < 2**Nand a list of integers{2**(N-1),2**(N-2),...,1}. Find the subset of the list of integers that sums toSsuch thaterror = r - Sis minimised.
选择总和为给定数字的2的幂(尽可能小的误差)只是整数的二进制编码.因此,该问题减少为整数的二进制编码.
>解的存在性：任何正浮点数r,0 <0. r< 2 ** N,可以转换为整数并以二进制形式表示.
>最优性：解的整数版本中的最大误差是±0.5的舍入误差. (在原始问题中,最大误差为±0.5 * 1/2 / N.)
>唯一性：对于任何正(浮点)数,都有唯一的整数表示,因此是唯一的二进制表示. (可能的例外是0.5 =见下文.)
实现(Python)
此函数将问题转换为整数等价,将r舍入为整数,然后将r的二进制表示作为整数读取以获得所需的分数.
def conv_frac (r,N):
# Convert to equivalent integer problem.
R = r * 2**N
S = int(round(R))
# Convert integer S to N-bit binary representation (i.e. a character string
# of 1's and 0's.) Note use of [2:] to trim leading '0b' and zfill() to
# zero-pad to required length.
bin_S = bin(S)[2:].zfill(N)
nums = list()
for index,bit in enumerate(bin_S):
k = index + 1
if bit == '1':
print "%i : 1/%i or %f" % (index,2**k,1.0/(2**k))
nums.append(1.0/(2**k))
S = sum(nums)
e = r - S
print """
Original number `r` : %f
Number of fractions `N` : %i (smallest fraction 1/%i)
Sum of fractions `S` : %f
Error `e` : %f
""" % (r,N,2**N,S,e)
样本输出：
>>> conv_frac(0.3141,10)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500
8 : 1/512 or 0.001953
Original number `r` : 0.314100
Number of fractions `N` : 10 (smallest fraction 1/1024)
Sum of fractions `S` : 0.314453
Error `e` : -0.000353
>>> conv_frac(0.30,5)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500
Original number `r` : 0.300000
Number of fractions `N` : 5 (smallest fraction 1/32)
Sum of fractions `S` : 0.312500
Error `e` : -0.012500
附录：0.5问题
如果r * 2 ** N以0.5结尾,则可以向上或向下舍入.也就是说,有两种可能的表示形式作为分数之和.
如果像原始问题陈述中那样,您希望使用最少分数的表示(即二进制表示中最少1位数),只需尝试两个舍入选项并选择更经济的选项.
