应用题-动态规划-最后一块石头的重量II( 01背包 )
- 版权声明：本站原创文章，于2026-05-14，由 管理员 发表。
- 转载请注明： 应用题-动态规划-最后一块石头的重量II( 01背包 ) | CodeGarden
```python
class Solution:
# 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
# 每一回合，从中选出任意两块石头，
# 然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
# - 如果 x == y，那么两块石头都会被完全粉碎；
# - 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
# 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
def lastStoneWeightII(self, stones: List[int]) -> int:
# 为了最后一块石头的重量最小
# 将石头分成两堆 保证两堆的质量差最小
# 最好的情况 就是石头堆可以分成相等的两部分, 总质量记为total
# 那么问题就转化为: 从stones中选择若干石头,使得背包( 最多装total//2的质量 )价值最大。( stones[i]即是质量也是价值。 )
total = 0
for v in stones: total += v
n = len( stones )
w = total // 2
dp = [ 0 for _ in range( w + 1 ) ]
for i in range( n ):
for j in range( w, stones[ i ] - 1, -1 ):
dp[ j ] = max( dp[ j ], dp[ j - stones[ i ] ] + stones[ i ] )
# 两个石头堆 质量之差就是最后石头最小重量
return abs( total - dp[ -1 ] - dp[ -1 ] )
```