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