[Vssue]1049.最后一块石头的重量II.md

[youngyangyang04]

https://www.programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html

[Du1in9]

// 例: stones = [2,4,1,1], w = 4
i = 0: stones[0] = 2, dp = [0,0,0,0,0]
    j = 4: dp[4] = 0, dp[2] = 0, 所以 dp[4] = max(0,2) = 2 (放物品0)
    j = 3: dp[3] = 0, dp[1] = 0, 所以 dp[3] = max(0,2) = 2 (放物品0)
    j = 2: dp[2] = 0, dp[0] = 0, 所以 dp[2] = max(0,2) = 2 (放物品0)
i = 1: stones[1] = 4, dp = [0,0,2,2,2]
    j = 4: dp[4] = 2, dp[0] = 0, 所以 dp[4] = max(2,4) = 4 (放物品1)
i = 2: stones[2] = 1, dp = [0,0,2,2,4]
    j = 4: dp[4] = 4, dp[3] = 2, 所以 dp[4] = max(4,3) = 4 (放物品1)
    j = 3: dp[3] = 2, dp[2] = 2, 所以 dp[4] = max(2,3) = 3 (放物品2, 放物品0)
    j = 2: dp[2] = 2, dp[1] = 0, 所以 dp[4] = max(2,1) = 2 (放物品0)
    j = 1: dp[1] = 0, dp[0] = 0, 所以 dp[4] = max(0,1) = 1 (放物品2)
i = 3: stones[3] = 1, dp = [0,1,2,3,4]
    j = 4: dp[4] = 4, dp[3] = 3, 所以 dp[4] = max(4,4) = 4 (放物品1)
    j = 3: dp[3] = 3, dp[2] = 2, 所以 dp[4] = max(3,3) = 3 (放物品2, 放物品0)
    j = 2: dp[2] = 2, dp[1] = 1, 所以 dp[4] = max(2,2) = 2 (放物品0)
    j = 1: dp[1] = 1, dp[0] = 0, 所以 dp[4] = max(1,1) = 1 (放物品2)
// 最终, 返回 8 - 2 * 4 = 0, 即最优解是粉碎完石头剩下重量为 0

[XingZuoMuYe]

选i块石头，使得他们的重量趋近于总重量的一半，因为这样和另一半抵消的差值就是最小的