# [leetcode/lintcode 题解] 算法面试真题详解：浮点数组合和

样例1

样例2

class Solution:
"""
@param A:
@param target:
@return: nothing
"""
def getArray(self, A, target):
dp=[100000.0 for i in range(target + 1)]
path = [[0 for i in range(len(A) + 1)]for i in range(target + 1)]
res = [0 for i in range(len(A))]
n = len(A)
dp[0] = 0.0
for i in range(n) :
for j in range(target,-1,-1) :
x , y = math.floor(A[i]) , math.ceil(A[i])
if j < x and j < y :
break
if j >= x and j >= y :                                        #两个物品均可以放入，必选其一
if dp[j - x] + A[i] - x < dp [j - y] + y - A[i] :
dp[j] = dp[j - x] + A[i] - x
path[j][i] = 1
else :
dp[j] = dp[j - y] + y - A[i]
path[j][i] = 2
elif j >= x:                                                        #只能放入向下取整整数，直接放入
dp[j] = dp[j - x] + A[i] - x
path[j][i] = 1
elif j >= y:                                                        #只能放入向上取整整数，直接放入
dp[j] = dp[j - y] + y - A[i]
path[j][i] = 2
if dp[target] >= 10000 :
return res
else :
ssum = target
for i in range(n - 1,-1,-1) :                #答案的记录此处通过对背包状态回溯完成还原(同样可以参考背包路径问题)。
if path[ssum][i] == 1 :
res[i] = math.floor(A[i])
ssum -= math.floor(A[i])
elif path[ssum][i] == 2 :
res[i] = math.ceil(A[i])
ssum -= math.ceil(A[i])
return res

+ 订阅