[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