Auto Layout on Android, A Pure Java Implementation

If you are familiar with IOS development, Auto Layout probably is not something new to you. But for those pure android geeks and others who are interested: “Auto Layout is a system that lets you lay out your app’s user interface by creating a mathematical description of the relationships between the elements. You define these relationships in terms of constraints either on individual elements, or between sets of elements. Using Auto Layout, you can create a dynamic and versatile interface that responds appropriately to changes in screen size, device orientation, and localization.” Quoted from Apple.

By reading a verbose definition won’t help much, an example may enlighten the concept better:

autolayout

In the above screenshot, we have a layout container (which has the screen size), and 3 different objects (views). To arrange such a layout via Auto Layout on IOS, we may simply define a few constraints:

(assume <container.padding> is a constant that represents the spaces between objects)

“green.top == container.top + <container.padding>”
“green.left == container.left + <container.padding>”
“green.width == (container.width – 3 * <container.padding>)  /  2”
“green.height == (container.height – 3 * <container.padding>) / 2”
“yellow.top == green.top”
“yellow.left == green.right + <container.padding>”
“yellow.width == green.width”
“yellow.height == green.height”
“blue.top == green.bottom + <container.padding>”
“blue.left == green.left”
“blue.right == container.right – <container.padding>”
“blue.height == green.height”

After we pass this set of constraints to the layout manager, the layout engine will do the math and solve out a best result that can satisfy each of these constraints. Thus a beautiful layout is rendered based on the calculated positions of each object.

Now it’s the point of this article: this awesome layout engine is now available on Android, and you can find the source code at Github: cassowary layout. It named cassowary because that is the original name of the algorithm, which also runs behind the Auto Layout of IOS. Yes, this android version library and the Auto Layout are sharing the same algorithm, which was developed by a few computer scientists back in 1990’s. Actually, there is a whole community behind this cassowary algorithm today: overconstrained. In there developers from all over the world have contributed to different ports of the same algorithm, and some of those implementations are already in use of many applications we are using daily today.

It is worth to mention that Cassowary layout listed above includes some android elements to handle the transition from mathematical calculated results to the actual sizes and positions of different views. If you simply just want to use the pure java implementation, I would suggest you to take a look at the math engine used by this cassowary layout library: cassowary-java. Alternatively, I personally prefer this re-designed implementation of the same algorithm: kiwi-java, which is declared as faster and smaller.

All these great libraries can be found at the cassowary community’s website: overconstrained

 

A powerful parser for Java and Android: Jparsec

Today I want to talk about a powerful Java parser: Jparsec (http://jparsec.codehaus.org/). I recently used it for one of my projects and found it really helpful. This article is mainly for students, who are still at school and have no industry experience. If you are already in Java development career for years, then you might already a user of this tool or at least met it before.

Back in school, whenever I needed to parse strings to capture inputs for my projects, I usually took the shortcut to make the development faster, by using the easiest way: str.split(). Normally a str.contains() command would be enough to help me judge whether the input string is the format my code required, then splitting the string to an array of words by defining delimiters finished the job.

This is an efficient approach when the project is small enough and while the input string format is rigidly controlled. If I ever encountered a more complex case, constructing a regex would be my final weapon to launch. I had never been to a circumstance that these methods failed on me, since all the projects was not at the engineering level yet.

However, these approaches became unacceptable for my first job. str.split() can only handle cases when delimiters are not complex, and if you can’t control the input format, things get worse because you never know what the string from user input looks like. Regex is hard to write at the first place and it’s even harder to maintain because it’s not human readable when it gets long and complicated. A experienced team member recommended Jparsec to me and it becomes my daily solution for parsing at these days.

Accurately speaking, Jparsec is a parser building tool. It helps you build mini java parsers quickly. The standout of Jparsec is its combinator nature. You can start building simple parsers such as whitespace parser, and then combine these simple parsers to a more complex parser. The way it works is just like the evolution of functional programming: Taking advantage of simple functions to generate the most powerful function!

Let’s see some codes:

/*
    ** fundamental parsers
     */


    // zero or more whitespace
    private static final Parser<String> whiteSpace() {
        return Scanners.string(" ").many().source();
    }

    //left parentheses
    private static final Parser<String> leftParen() {
        return whiteSpace().followedBy(Scanners.string("(")).followedBy(whiteSpace());
    }

    //right parentheses
    private static final Parser<String> rightParen() {
        return whiteSpace().followedBy(Scanners.string(")")).followedBy(whiteSpace());
    }

    //comma
    private static final Parser<String> comma() {
        return whiteSpace().followedBy(Scanners.string(",")).followedBy(whiteSpace());
    }

    //dot
    private static final Parser<String> dot() {
        return whiteSpace().followedBy(Scanners.string(".")).followedBy(whiteSpace());
    }

    //negative sign
    private static final Parser<String> negativeSign() {
        return whiteSpace().next(Scanners.string("-").source()).optional().followedBy(whiteSpace());
    }

As seen in the code, we first built a whitespace parser, it scans for ” ” zero or many times, and returns the scanned whitespace(s) as a string(by using source()). I won’t talk much on the syntax and APIs since they are basically human readable and you can find pretty much you need in the documentation listed at the beginning of this article.

Later on, we used the similar way to generate more fundamental parsers such as parentheses, comma, and dot. Note how we generate these parsers by taking advantage of the whitespace parser we built earlier: each parentheses, comma and dot can comes after whitespace, and followed by more whitespace. We are now in the evolution!

Let’s together see a more complex case:

//decimal number with possible negative sign
    private static final Parser<Integer> integer() {
        return Parsers.sequence(negativeSign(), Scanners.INTEGER, new Map2<String, String, Integer>() {
            public Integer map(String neg, String value) {
                if (neg != null) {
                    return -Integer.parseInt(value);
                } else {
                    return Integer.parseInt(value);
                }
            }
        });
    }

In the above code, we generated a parser that parses negative integers. Whenever we see a negative sign followed by an integer, we create a map to translate these inputs to the result we want(in this case a negative integer). The map defines three parameter types, the first two comes from the parsers in the sequence. and the last parameter type is the result(return) type. Inside the map method, we can do whatever we want to generate the ideal result. In this case, if we see a negative sign, we return the negative value of the value we got from the second parser in the sequence, otherwise we return this value directly.

In the end, if we want to parse a string “-5”, we write:

int result = integer().parse("-5"); 

We got result = -5.

Here I’m only showing a basic example, but you can already see the power of Jparsec. You can use it to define your own gramma and parse whatever value you want from any kind of string input format. It’s much more human readable than regex, and it’s much more reliable than str.split().

Have fun with Jparsec!

Android: RecyclerView and its Custom LayoutManager

It has been a few months now since the RecyclerView was introduced by Google last year, and finally I got a chance to play with it. This article is mainly focused on building a custom LayoutManager for the RecyclerView. I’ll skip most of fundamental parts of RecyclerView because there are many such tutorials already available on the Internet.

Starting with basics:

Per Google’s definition, RecyclerView is “a flexible view for providing a limited window into a large data set”. In other words, It is a more advanced and flexible version of ListView, or more generally speaking, it’s a CollectionView that handles a collection of child views. Everything you do with ListView you can also use RecyclerView to replace, but with more flexible layout management and animation effects. If you haven’t learnt all these stuff, I suggest to take a look at this tutorial.

Similar to ListView, a RecyclerView requires a adapter to bind data to views. In this case, the adapter needs to extend RecyclerView.Adapter class. In addition, you need to set a LayoutManager to your RecyclerView for measuring and laying out all child views within the RecyclerView. This step seems to be extra work appending to ListView, but it gives you more power to handle the layout to look exact like the way you want it. The LayoutManager also needs to determine the right time to recycle a view when it’s not visible anymore. We will discuss this in the following sample.

A sample adapter implementation is already listed in the tutorial mentioned above, take a close look then you will realize it’s just like the adapter for ListView, but enforces the ViewHolder mechanism. It’s very clear to follow so I will skip this part.

By default, Android supports 3 LayoutManagers: LinearLayoutManager, GridLayoutManager, and StaggeredGridLayoutManager. What if you want something more flexible? You can implement your own LayoutManager by extending RecyclerView.LayoutManager. Next let’s walk through a sample custom LayoutManager that places child views at predefined locations, while recycle views that are no longer visible and re-use them when a same type of view need to be shown.

After you created your LayoutManager class, the only required override method is:

@Override
public RecyclerView.LayoutParams generateDefaultLayoutParams() {
    return new RecyclerView.LayoutParams(
            RecyclerView.LayoutParams.WRAP_CONTENT,
            RecyclerView.LayoutParams.WRAP_CONTENT);
}

It basically creates a default LayoutParams for the RecyclerView. Now your LayoutManager is compilable!

Starting from here, things get more interesting. The next important method you probably want to override is:

@Override
public void onLayoutChildren(RecyclerView.Recycler recycler, RecyclerView.State state) {

}

this method is called when the child views are initially placed, and when the adapter’s dataset changes. In our sample case, we want it to layout all visible children.

@Override
public void onLayoutChildren(RecyclerView.Recycler recycler, RecyclerView.State state) {
    fillVisibleChildren(recycler);
}

private void fillVisibleChildren(RecyclerView.Recycler recycler){
    //before we layout child views, we first scrap all current attached views
    detachAndScrapAttachedViews(recycler);

    //layoutInfo is a Rect[], each element contains coordinates for a view.
    for(int i = 0; i < layoutInfo.length; i++){
        if(isVisible(i)){
            View view = recycler.getViewForPosition(i);
            addView(view);
            layoutDecorated(view, layoutInfo[i].left, layoutInfo[i].top - verticalScrollOffset, layoutInfo[i].right, layoutInfo[i].bottom - verticalScrollOffset);
        }
    }
}

/*determine whether a child view is now visible
**getVerticalSpace() and getHorizontalSpace() returns layout space minus paddings.
**verticalScrollOffset and horizontalScrollOffset are current offset distances
**according to the initial left top corner, before any scrolling.
*/
private boolean isVisible(int index){
    if(layoutInfo[index].bottom < verticalScrollOffset
            || layoutInfo[index].top > getVerticalSpace() + verticalScrollOffset
            || layoutInfo[index].right < horizontalScrollOffset
            || layoutInfo[index].left > getHorizontalSpace() + horizontalScrollOffset){
        return false;
    }
    else{
        return true;
    }
}

At this point, you already have the initial layout setup, all visible child views are now on your screen!

The next step is to enable scrolling, this is a RecyclerView after all!

To enable scrolling, you need to override the following two methods, depending on your scroll direction:

@Override
public boolean canScrollHorizontally() {
    return true;
}

@Override
public boolean canScrollVertically() {
    return true;
}

This will give your layout scrolling ability, but we need to tell the LayoutManager what to change after we scroll. Let’s keep going, override the following methods:

@Override
public int scrollHorizontallyBy(int dx, RecyclerView.Recycler recycler, RecyclerView.State state) {
    int travel;
    final int leftLimit = 0;
    final int rightLimit = findRightLimit(); //a helper method to find the rightmost child's right side.
    if(dx + horizontalScrollOffset < leftLimit){
        travel = horizontalScrollOffset;
        horizontalScrollOffset = leftLimit;
    }
    else if(dx + horizontalScrollOffset + getHorizontalSpace() > rightLimit){
        travel = rightLimit - horizontalScrollOffset - getHorizontalSpace();
        horizontalScrollOffset = rightLimit - getHorizontalSpace();
    }
    else{
        travel = dx;
        horizontalScrollOffset += dx;
    }
    fillVisibleChildren(recycler);
    return travel;
}

@Override
public int scrollVerticallyBy(int dy, RecyclerView.Recycler recycler, RecyclerView.State state) {

    int travel;
    final int topLimit = 0;
    final int bottomLimit = findBottomLimit();//a helper method to find the bottommost child's bottom side.
    if(dy + verticalScrollOffset < topLimit){
        travel = verticalScrollOffset;
        verticalScrollOffset = topLimit;
    }
    else if(dy + verticalScrollOffset + getVerticalSpace() > bottomLimit){
        travel = bottomLimit - verticalScrollOffset - getVerticalSpace();
        verticalScrollOffset = bottomLimit - getVerticalSpace();
    }
    else{
        travel = dy;
        verticalScrollOffset += dy;
    }
    fillVisibleChildren(recycler);
    return travel;
}

The dx and dy parameter in these two methods are the distances to scroll in pixel. dx increases as scroll position approaches the right. dy increases as scroll position approaches the bottom. These two methods return the actual distance travelled. As boundary limitations, the returned distance may be smaller than dx or dy. We have to handle the boundary cases by ourselves, simple math though.

getVerticalSpace();
getHorizontalSpace();

returns the available space of the visible area, for example, a normal getVerticalSpace() implementation returns  getMeasuredHeight() – getPaddingTop() – getPaddingBottom().

verticalScrollOffset and horizontalScrollOffset are local variables that keep a record of the current scrolling offset. Every time you scroll the view these values get updated. These values are used when we calculate if a child view is currently visible. See

private boolean isVisible(int index)

above for example.

After we return the actual scrolled distance, we update locations for all child views, by calling fillVisibleChildren() again.

Now you have your first custom LayoutManager for RecyclerView. See how simple it is!

If you are interested in more complex cases: you can take a look at this blog, which introduce a custom grid LayoutManager.

关于二分查找(Binary Search)及其变种形式的总结

二分查找是基本算法,但是据统计只有10%的程序员可以写出没有bug的代码。出错的原因主要集中在对边界值得选择和判定条件上,一不小心就可能导致超出边界或者死循环的情况。这里作如下总结:

标准版二分查找:
在有序(非降序)数组中查找一个target值,数组中元素没有重复,找到target则返回该元素对应的index,找不到则返回-1。

注意1:如果是start < end,那么当target等于num[num.length-1]时,会找不到该值。 注意2:因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid,能不能写成end = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成end = mid,当循环到start = 0, end = 0时(即num[start] = 1, num[end] = 1时),mid将永远等于0,此时end也将永远等于0,陷入死循环。也就是说寻找target = -2时,程序将死循环。

注意3:因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid,能不能写成start = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。也就是说寻找target = 9时,程序将死循环。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

二分查找变形一:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最小值,找不到则返回-1。

注意1:为了对左右相邻的两个数进行对比,循环结束的时候,start和end应该相隔1。

注意2:a). 当num[mid] == target时,此时并不能直接返回mid,因为有可能num[mid-1]或者num[mid-2]…也等于target,所以此时应该将end  = mid,然后继续循环。b). 当num[mid] > target时,如果有num[index] == target,那么index一定小于mid,本来按此道理应该令end = mid – 1,但是为什么此处可以end = mid呢?回头去看上一题(标准版)的注意2,只有当start = end时,才会出现死循环的情况。这里因为while循环的限制条件使得start和end永远不可能相等,所以end = mid也是正确的。由此,我们可将a) 和 b) 两种情况合并。

注意3:这里与上题一致,不用有变化。但是在这里写成start = mid也是成立的,为啥呢?回头看上题的注意3,同样的例子num = {1, 2, 5, 7, 9}; 在上题中,如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。但在此题中由于while中的限制条件的变化,避免了这种死循环的发生。

注意4:此处为什么要分别检验num[start]和num[end]是否等于target呢?因为这两个值都有可能等于target,取决于中间二分时start和end的更新过程。这里随便用几个简单的例子即可验证。如果循环结束时num[start] == num[end] == target,根据题意应该返回start,所以我们先验证start。如果两个值都不是target,则target不存在,返回-1。

public int binarySearchMinimumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意2
            end = mid;
        }
        else{
            start = mid + 1; //注意3
        }
    }
    if(num[start] == target) //注意4
        return start;
    else if(num[end] == target)
        return end;
    else
        return -1;
}

二分查找变形二:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最大值,找不到则返回-1。

道理与上一题相同,只要在注意2和注意3处与上题反过来就行了,原理不重复了,拿不准的时候可以用几个简单的test case测试一下。

public int binarySearchMaximumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){ //注意2
            start = mid;
        }
        else{
            end = mid - 1; //注意3
        }
    }
    if(num[end] == target)
        return end;
    else if(num[start] == target) //注意4
        return start;
    else
        return -1;
}

二分查找变形三:
在有序(非降序)数组中查找一个可能的”最大”index,使得num[index] < target,数组中元素可能有重复,找不到则返回-1。

注意1:我们可以对此步分开考虑,当num[mid] == target时,因为我们要求num[index] < target,所以index必须在mid左边。当num[mid] > target时,target肯定在num[mid]的左边,所以index肯定也要在mid的左边。那么再多想一步,假如num[mid] >= target时,我们进行了end = mid的操作,会产生什么后果呢?经我的有限测试,好像并没有什么问题,因为while中的限制条件导致了每当start + 1 == end的时候,循环就结束了,所以标准版二分查找中出现的死循环的情况并不存在。

注意2:当num[mid] < target时,为什么此处用start = mid而不是start = mid + 1?因为有可能num[mid+1] == target,此时如果start = mid + 1, 则num[start] == target,明显错过了正解。

public int binarySearchClosestFromLeft(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意1
            end = mid - 1;
        }
        else{ //注意2
            start = mid;
        }
    }
    if(num[end] < target){
        return end;
    }
    else if(num[start] < target){
        return start;
    }
    else{
        return -1;
    }
}

二分查找变形四:
在有序(非降序)数组中查找一个可能的”最小”index,使得num[index] > target,数组中元素可能有重复,找不到则返回-1。
道理与上题完全相同,稍作调整即可。

注意1:此处同上题注意1原理相同,写成start = mid也应该没有问题。

public int binarySearchClosestFromRight(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){
            start = mid + 1; //注意1
        }
        else{
            end = mid;
        }
    }
    if(num[start] > target){
        return start;
    }
    else if(num[end] > target){
        return end;
    }
    else{
        return -1;
    }
}

综上所述,总结规律:
1. 当数组中没有重复元素时:while循环判定条件是(start <= end),每次start更新为mid + 1,end更新为mid – 1。
2. 当数组中含有重复元素时或者要找的值是target的相邻数时,判定条件是(start + 1 < end),当num[mid] == target时,并不返回mid,而是根据情况跟新start或者end。每次start更新为mid,end也更新为mid即可。

Fast Power, LintCode

Calculate the an % b where a, b and n are all 32bit integers.

Example
For 231 % 3 = 2

For 1001000 % 1000 = 0

Challenge
O(logn)

数学问题,要求O(log n)的时间复杂度,也就是每次去掉一半的计算量,先要找到对应的数学公式:
(a * b) % p = (a % p * b % p) % p

所以(a^n)%b = (a^n/2 * a^n/2 * a) % b = ((a^n/2 * a^n/2)%b * a%b) % b
注意int和long的转化,防止溢出。

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        // write your code here
        long ret = getPower(a, b, n);
        return (int)ret;
    }
    public long getPower(int a, int b, int n){
        if(a == 0) return 0;
        if(n == 0) return 1 % b;
        if(n == 1) return a % b;
        
        long ret = getPower(a, b, n/2);
        ret *= ret;
        ret %= b;
        if(n % 2 == 1){
            ret = ret * (a % b);
        }
        return ret % b;
    }
};

Binary Search Duplicated Values

Binary search is easy, but what if there are duplicated elements in the sorted array and you need to find the first index of the target value?

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        while(left < right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                result = mid;
                right = mid;
            }
            else if(nums[mid] > target){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return result;
    }
}

Backpack II, LintCode

Given n items with size A[i] and value V[i], and a backpack with size m. What’s the maximum value can you put into the backpack?
Note
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

背包问题是一个经典的算法问题,可以用动态规划的方法来解,网上找到的最好的解释是:
http://love-oriented.com/pack/P01.html
基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度
以上方法的时间和空间复杂度均为O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O。

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。

事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。

过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。

有了这个过程以后,01背包问题的伪代码就可以这样写:

for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。

一个常数优化
前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进。

由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可。以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的

for i=1..N
for v=V..0
可以改成

for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。

小结
01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[][] dp = new int[A.length+1][m+1];
        for(int i = 0; i <= A.length; i++){
            for(int j = 0; j <= m; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                }
                else if(A[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }
}