描述
给出一个小数数组A，一个非负整数target。对A中的每个小数进行向上取整或者向下取整的操作，最后得到一个整数数组，要求整数数组的所有数字和等于target，并且要求对小数数组的调整和最小。
例如ceil(1.2)，则调整数为0.8；floor(1.2)，则调整数为0.2。返回该整数数组。
在线评测地址：领扣题库官网
样例1
输入：A=[1.2,1.3,2.3,4.2],target=9
输出：[1,1,3,4]
解释：1.2->1,1.3->1,2.3->3,4.2->4。样例2
输入：A=[2.5,2.5],target=5
输出：[2,3]
解释：2.5->2,2.5->3.解题思路
类比于分组背包问题，每个数字可以看成是包含两个互斥的物品放入即可。对于每个小数，看作是向上取整和向下取整的两个物品，必须选择一个，考虑分组背包。在第二层循环即背包容量的循环中同时考虑两个物品，则可保证选择具有互斥性。
源代码
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更多题解参考：九章官网solution
