1049最后一块石头的重量II

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 将问题转化为，尽可能把石头 分成两堆一样重的情况，转化为 0-1背包问题。
        # 定义 d[i] 为 i 容量的背包中，能装的最大价值。 这里 i的 重量、价值 共用一套数值；
        target = sum(stones)//2
        d = [0]*(target+1)
        for i in range(len(stones)):
            for j in range(target,stones[i]-1,-1):
                d[j] = max(d[j],d[j-stones[i]]+stones[i])
        print(sum(stones),target,d)
        return sum(stones)-d[target]-d[target]