BackPack

I

http://www.lintcode.com/en/problem/backpack/#

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Wrong solution:

State: res[i][j] means the maximum size using first i items to fill backpack of size j

why wrong:

the items are used repeatedly in this solution

public int backPack(int m, int[] A) {
        // write your code here
        if (A.length == 0) {
            return 0;
        }
        Arrays.sort(A);
        int[] a = new int[m+1];
        //int[] b = new int[A.length];
        a[0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = A.length-1; j >= 0; j--) {
                if (i >= A[j]) {
                    a[i] = Math.max(a[i], a[i-A[j]] + A[j]);
                }
            }
        }
        return a[m];
    }

Solution: 2D DP I

Note: the state should be:

d[i][j] means whether size j can be filled using first i items

d[i][j] = d[i-1][j] || (j>=A[i-1] && d[i-1][j-A[i-1]]).

public int backPack(int m, int[] A) {
 8         // write your code here
 9         boolean[][] res = new boolean[A.length+1][m+1];
10         res[0][0] = true;
11         for (int i=1; i<=A.length; i++) {
12             for (int j=0; j<=m; j++) {
13                 res[i][j] = res[i-1][j] || (j-A[i-1]>=0 && res[i-1][j-A[i-1]]);
14             }
15         }
16         for (int j=m; j>=0; j--) {
17             if (res[A.length][j]) return j;
18         }
19         return 0;
20     }

Solution II: 1D DP

d[i][j] = d[i-1][j] || (j>=A[i-1] && d[i-1][j-A[i-1]]) can be reduced to :

d[j] = d[j] || (j>=A[i-1] && d[j-A[i-1]])

since the state function only has d[i] and d[i-1], but note that j must decrease from m to 0 to avoid overwriting d[j-1]

public int backPack(int m, int[] A) {
 8         if (A.length==0) return 0;
 9         
10         int len = A.length;
11         boolean[] size = new boolean[m+1];
12         Arrays.fill(size,false);
13         size[0] = true;
14         for (int i=1;i<=len;i++)
15             for (int j=m;j>=0;j--){
16                 if (j-A[i-1]>=0 && size[j-A[i-1]])
17                     size[j] = size[j-A[i-1]];
18             }
19 
20         for (int i=m; i>=0;i--)
21             if (size[i]) return i;
22 
23         return 0;
24     }

II

http://www.lintcode.com/en/problem/backpack-ii/

A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

1) Optimal Substructure: To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set. Therefore, the maximum value that can be obtained from n items is max of following two values. 1) Maximum value obtained by n-1 items and W weight (excluding nth item). 2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        if (A.length == 0 || A.length != V.length) {
            return 0;
        }

        int[] res = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j >= 1; j--) {
                int k = j >= A[i] ? res[j-A[i]] + V[i] : 0;
                res[j] = Math.max(res[j], k);
            }
        }
        return res[m];
    }