碰到了一道optimal partition的题想请教大家

maplain 发表于 2015-10-17 07:53
我的想法是：
1. sort;
2. 输出相同元素的个数，组成一个新的array；

喔喔，非常感谢地理大神！！受教了。。自己还是太嫩啊。

DP应该也可以。
先记录每个元素的出现次数(key, count)， 然后按照key排序存一个数组A
用L[i,k]记录用最优解将第0-i个元素放到k个bin里时的最后一个bin包含的元素个数，G[i,k]记录最大bin里的元素个数
更新L[i,k]和G[i,k]要做以下判断
如果L[i-1, k]+A[i]<=G[i-1,k]，那么最优放法就是L[i,k]=L[i-1,k]+A[i], G[i,k]=G[i-1,k]
如果L[i-1,k]+A[i]>G[i-1,k]，那么就可能有两种放法，最优放法要取其中之一：
方法1: 前面i-1个元素放到k个bin里，然后元素i也放到bin k里，bin k的元素总数是 s1 = L[i-1,k]+A[k]
方法2: 前面i-1个元素放到k-1个bin里，然后元素i单独放到bin k里， bin k的元素总数是 s2 = A[k]
如果s1<max(s2,G[i-1,k-1])，那就选方法1，L[i,k] = L[i-1,k]+A[k], G[i,k] = L[i,k]
如果s1>max(s2, G[i-1, k-1])，那就选方法2, L[i,k] = A[k], G[i,k] = max(L[i,k], G[i-1, k-1])
如果s1==max(s2, G[i-1, k-1])，那就随便选1或者2

最后要求的就是G[m-1, n-1], m是distinct元素的个数，n是bin的个数

gorilazz 发表于 2015-10-18 13:00
DP应该也可以。
先记录每个元素的出现次数(key, count)， 然后按照key排序存一个数组A
用L记录用最优解将 ...

附上code:

class Solution(object):
    def placement(self, nums, n):
        
        numbers = {key:nums.count(key) for key in nums}
        numbers = [(key, numbers[key]) for key in numbers]
        numbers.sort()

        A = [item[1] for item in numbers]
        
        if len(numbers)<=n:
            return max(A)

        L = [[0]*n for _ in range(len(A))]
        G = [[0]*n for _ in range(len(A))]

        L[0][0] = A[0]
        G[0][0] = A[0]
        for i in range(1, len(A)):
            L[i][0] = L[i-1][0] + A[i]
            G[i][0] = L[i][0]

        for i in range(len(A)):
            if i>=n:
                break
            L[i][i] = A[i]
            G[i][i] = max(A[:i+1])

        for i in range(len(A)):
            for j in range(i+1, n):
                L[i][j] = 0
                G[i][j] = G[i][i]

        for i in range(1,len(A)):
            for j in range(1,i):
                if j>=n:
                    break
                tmp = L[i-1][j] + A[i]
                if tmp<=G[i-1][j]:
                    L[i][j] = tmp
                    G[i][j] = G[i-1][j]
                elif tmp<=max(G[i-1][j-1], A[i]):
                    L[i][j] = tmp
                    G[i][j] = G[i-1][j]
                else:
                    L[i][j] = A[i]
                    G[i][j] = max(G[i-1][j-1], A[i])

        return G[len(A)-1][n-1]

sol = Solution()
nums = [1,1,1,1,1,1]
result = sol.placement(nums, 3)
print(result)

gorilazz 发表于 2015-10-18 13:26
附上code:

class Solution(object):

感谢大神耐心解答！！