Backpack

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

注意

You can not divide any item into small pieces.

样例

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.

标签 Expand 

Dynamic Programming  LintCode Copyright

解法思路：

将所有数据以及数据的累加和映射到一个数组中，则数组中的最大值就是可以目标值！

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        if (A.length==0) return 0;
        
        int len = A.length;
        boolean[] size = new boolean[m+1];
        Arrays.fill(size,false);
        size[0] = true;
        for (int i=1;i<=len;i++)
            for (int j=m;j>=0;j--){
                if (j-A[i-1]>=0 && size[j-A[i-1]])
                    size[j] = size[j-A[i-1]];
            }
 
        for (int i=m; i>=0;i--)
            if (size[i]) return i;
 
        return 0;
    }
}

Backpack II

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?

注意

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

样例

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.

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[]) {
		int vs[] = new int[m]; // value 累加数组
		Arrays.fill(vs, 0);

		for (int i = 0; i < A.length; i++) {
			for (int j = m - 1; j > A[i]; j--) {
				if (vs[j - A[i]] > 0) {
					int tmp = vs[j - A[i]] + V[i];
					if (vs[j] < tmp || vs[j] == 0)
						vs[j] = tmp;
				}
			}
			if (vs[A[i]-1] == 0 || vs[A[i]-1] < V[i])
				vs[A[i]-1] = V[i];
		}

		int max = 0;
		for (int i = m - 1; i >= 0; i--)
			if (vs[i] > max)
				max = vs[i];
		return max;
	}
}