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

描述
给出一个小数数组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

本文转自网络，原文链接：https://developer.aliyun.com/article/783997
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！