leetcode 1049： 最后一块石头的重量 II
题目描述：每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果x != y，那么重量为x的石头将会完全粉碎，而重量为 y 的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
输入：[2,7,4,1,8,1]
输出：1
解题步骤：该题可以转化成，将该数组分成两个集合，两个集合之差最小，集合之差最小为0.所以要找到最小差，可以转化成找到一个集合之和最接近数组总和的一半。也就是当背包容积为数组总和一半的时候bagv，此时所选择集合的最大值。
1、 状态定义：dp[i][j]表示从前i个数值中选择出的容积小于bagv的最优石头总重量，j表示剩余背包容量
2、 状态转移方程：
If(j < stones[i]) dp[i][j] = dp[i-1][j]
Else dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])
3、 初始化：初始化第1行dp数组，表示第一个数是否能够添加到容积为i的背包中
4、 输出：sum – 2*dp[][bagv]
代码：