Backpack V

题目

563. Backpack V
     Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible fill the backpack.

Each item may only be used once

Example
Given candidate items [1,2,3,3,7] and target 7,

A solution set is:
[7]
[1, 3, 3]
return 2

答案

Backpack题是要找出最大不超过target的物品重量sum
而这个Backpack V题是要找出有多少种物品重量sum刚好等于target

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        int m = target, n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        
        f[0][0] = 1;
        for(int i = 1; i <= m; i++) f[0][i] = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if(j >= nums[i - 1])
                    f[i][j] += f[i - 1][j - nums[i - 1]];
            }        
        }
        
        return f[n][m];
    }
}

空间优化

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers
     * @param target: An integer
     * @return: An integer
     */
    public int backPackV(int[] nums, int target) {
        int m = target, n = nums.length;
        int[] f = new int[m + 1];
        
        f[0] = 1;
        for(int i = 1; i <= m; i++) f[i] = 0;
        
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= 0; j--) {
                if(j >= nums[i - 1])
                    f[j] += f[j - nums[i - 1]];
            }        
        }
        
        return f[m];
    }
}