1. Description

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

Notice

You can not divide any item into small pieces.

2. Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11,
we can select [2, 3, 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.

3. Code

public class LintCode0092 {
    public int backPack(int m, int[] A) {
        if (m < 0 || A == null || A.length == 0) {
            return 0;
        }

        int[][] dp = new int[A.length + 1][m + 1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i + 1][j] = dp[i][j];
                if (j >= A[i]) {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - A[i]] + A[i]);
                }
            }
        }

        return dp[A.length][m];
    }

    public static void main(String[] args) {
        LintCode0092 lintcode = new LintCode0092();
        int[] A = new int[] { 3, 4, 8, 5 };
        System.out.println(lintcode.backPack(10, A));
    }
}