1049. Last Stone Weight II

Here is my post written on Oct. 8, 2019

Oct. 8, 2019 9:11 PM
It is the first submission I made by studying one of solutions written in Chinese. I still have several concerns in terms of implementation.

In order to fully understand the algorithm, I asked myself why the second for loop is looping from sum/2 to current variable value, can we do increasing order from current variable value to sum/2 instead. I changed the code, and then one of test cases fails.

I need to look into and be able to explain the above failed test case to change for loop from decreasing order to increasing order. I need to ask a few questions, and work on basics first.

I will come back and update the post based on better understanding of the algorithm.

public class Solution {
    /// <summary>
        /// study code
        /// https://www.acwing.com/solution/LeetCode/content/2139/
        /// I like to read comment written in Chinese. I like to write good comment like this 
        /// as well one day. 
        /// (动态规划) O(n×sum)
        /// 合并的过程就是给每个重量前赋值正号或者负号的过程，相当于把这些石头分为两组，
        /// 使得两组的差值尽可能小，所以这是经典的集合划分NP完全问题，可以采用动态规划的方法求解。
        /// 设状态 f(i) 表示是否存在一个划分，使得某组的重量综合为 ii。
        /// 初始时 f(0)=true，其余为 false。
        /// 转移时，模仿01背包的算法，对于每个物品，有放和不放两种决策，故 
        /// f(j)=f(j)|f(j−stones[j])。
        /// 最终答案需要枚举，j 从 sum/2 开始到 0，如果 f(j)==true，则返回 sum−j−j。
        /// 时间复杂度
        /// 状态数为 O(n×sum)，转移数为常数，故时间复杂度为 O(n×sum)。
        /// 空间复杂度
        /// 需要额外 O(n) 的空间构造堆。
        /// </summary>
        /// <param name="stones"></param>
        /// <returns></returns>
        public int LastStoneWeightII(int[] stones)
        {
            var length = stones.Length;
            var sum = stones.Sum();

            var found = new bool[sum + 1];
            found[0] = true;

            // transition formula - figure out the reasoning later
            for (int i = 0; i < length; i++)
            {
                var current = stones[i];
                for (int j = sum / 2; j >= current; j--)
                {
                    found[j] = found[j] | found[j - current];
                }
            }

            // Find maximum sum less and equal to sum/2. 
            for (int i = sum / 2; i >= 0; i--)
            {
                if (found[i])
                {
                    return sum - i - i; 
                }
            }

            return sum; 
        }
}

Actionable Items

It takes time to figure out the analysis how to come out the idea why using descending order is a must in second for loop. I had to go through rigorously thinking in order to understand the process. So I understand that it is time consuming process to figure out why.

Learning Knapsack algorithm turns into such great experience, since I try to challenge myself; try the different idea, failed test case, and then push myself to explain it. I could not explain it on Oct. 8, 2019. It turned out so clear to me next day.