[アルゴリズム][ダイナミックプランニング]リュックサック問題変異体-均一プレゼント

贈り物を均等に分ける
今日出会った面接官は問題を引き裂いた.
プレゼント価値リストを指定するには、2つのサブセットの価値和の差が最小になるように、2つのサブセットに分割する必要があります.
構想
[アルゴリズム][ダイナミックプランニング][リュック問題①] 0-1リュック問題の最適化と制約変形[python実現

は、0-1リュックサックの問題と見なしています.

総価値の半分をリュックサック容量として

このリュックサックをできるだけ埋め尽くす(この問題ではw i w_i wi=v i v_i vi)

d p [ j ] = m a x { d p [ j − w i ] + v i , d p [ j ] } dp[j]=max\{dp[j−w_i]+v_i ,dp[j]\} dp[j]=max{dp[j−wi​]+vi​,dp[j]}

総価値から半リュックサックの最適価値を差し引くと

になります.
コード#コード#

class Solution:
    def maxPresent(self , presentVec):
        #              
        all_volume = sum(presentVec)
        half_volume = all_volume//2
        dp = [0] * (half_volume+1)
        for w in presentVec:#  i   
            for j in range(half_volume, w-1, -1):
                dp[j] = max(dp[j], w + dp[j-w])
        return all_volume - 2*dp[-1]

2つのサブセットの具体的なアイテムの内容を出力するように要求された場合:

class Solution:
    def maxPresent(self , presentVec ):
        #              
        all_volume = sum(presentVec)
        half_volume = all_volume//2
        dp = [0] * (half_volume+1)
        trace = [[] for _ in range(half_volume + 1)] #       
        for w in presentVec:#  i   
            for j in range(len(dp)-1, w-1, -1):
                new_price = w + dp[j-w]
                if new_price > dp[j]:
                    dp[j] = new_price
                    trace[j] = trace[j-w] + [w] #     
        return all_volume - 2*dp[-1], trace[-1] #            

テスト:

s = Solution()
print(s.maxPresent([41,467,334,1,169,224,478,358])) 
#      0，       ：[334, 224, 478]