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

Note

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Analysis:

DP.

boolean d[i][j]: From the first i items, can we select some items so that their weight equals to j.

d[i][j] = d[i-1][j] || d[i-1][j-A[i-1]].

d[0][0] = true;

We can use 1D array to perform the DP.

d[j] = d[j] || d[j-A[i-1]].

NOTE: for 1D array, the j must be decreased from m to 0 rather increasing from 0 to m!

Solution:

1 public class Solution { 2     /** 3      * @param m: An integer m denotes the size of a backpack 4      * @param A: Given n items with size A[i] 5      * @return: The maximum size 6      */ 7     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     }25 }